[BinarySearch] 수들의 합

서로 다른 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)

 

 

hose0728.tistory.com/85

백준 알고리즘 1789번 수들의 합 풀이 With Python