728x90
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
N의 최댓값을 구해야되기 때문에
자연수의 합이 주어졌을 때 가장 작은 수 부터 차례로 더하면서 그 합이 S를 넘기 직전의 개수를 출력하면 된다.
1부터 N까지의 합은 N(N+1) / 2
N이 1일때를 제외하고 N(N+1) / 2 <= S이기 때문에
end = S로 설정하고 이진탐색을 수행하면 된다.
s = int(input())
start = 1
end = s
answer = 0
while start <= end:
mid = (start + end) // 2
if mid*(mid+1)//2 <= s:
answer = mid
start = mid + 1
else:
end = mid - 1
print(answer)
728x90
'BOJ' 카테고리의 다른 글
[BinarySearch] K번째 수 1300번 (0) | 2020.12.03 |
---|---|
[BinarySearch] 가장 긴 증가하는 부분 수열 2 (0) | 2020.12.03 |
[BinarySearch] 공유기 설치 (0) | 2020.12.01 |
[BinarySearch] 예산 (0) | 2020.11.29 |
[BinarySearch&Counter] 숫자 카드 2 (0) | 2020.11.27 |
댓글