portrait4521   11달 전

층마다의 최댓값 간격이 등차수열이길래

그걸 이용하여 반복문 돌려 일일이 찾는 방법으로 해결했는데

더 잘 푸는 방법이 있을까요?

아시는 분은 약간의 힌트만 주시면 감사하겠습니다..

bupjae   11달 전

10~12번째 줄의 반복문에서 3i2 -3i +1 >= n 를 만족하는 i의 최소값을 구하고 있는데

이걸 반복문을 사용하지 않고 구할 방법을 묻는 것인가요?

.

만약 그렇다면, 2차방정식의 근의 공식을 이용하면 반복문 없이 i의 값을 바로 구할 수 있고

근의 공식을 통해 구한 i는 일반적으로 실수로 나올테니, 부등호의 방향에 맞추어 가장 가까운 정수로 올리거나 버리면 될 것 같습니다

portrait4521   11달 전

아 실수로 나와서 근의 공식을 못 쓴다고 생각했는데

정수로 만들어 볼 생각을 못했네요 감사합니다

wlaud   11달 전

https://www.acmicpc.net/proble...

이러한 방식으로 풀 수 있는 문제도 있습니다.

portrait4521   11달 전

감사합니다.

prarie   11달 전

문제 내용은 모르지만, 3i2 -3i +1 은 양수에서 증가하는 함수기 때문에 이분탐색을 적용할 수 있습니다.

[1, Max] 에서 중간값 x를 뽑은 뒤 3x^2 - 3x + 1 이 n보다 큰지 작은지 확인하면 탐색 범위를 반으로 줄일 수 있습니다


제곱근을 찾을 때 등 다양한 상황에 적용할 수 있습니다

portrait4521   11달 전

으악 아직 이분탐색 문제는 안 풀어봤는데..

나중에 참고하겠습니다 고마워용

댓글을 작성하려면 로그인해야 합니다.