백준(1789) - 수들의 합 Python

백준(1789) - 수들의 합

문제풀이: 이진탐색, 파이썬

해결방법

예시)

# 입력 #
200

# 출력결과 #
19

• end를 930000 으로 정한 것은 문제의 s의 최대 값이 4,294,967,295 이기 때문에 대충 계산해보고 설정한 것 이다.

s = int(input())

dp = [0] * 930001
cnt = 0
for i in range(1, 930000):
    cnt += i
    dp[i] = cnt

start = 0
end = 930000

while start <= end:
    mid = (start + end) // 2
    if dp[mid] > s:
        end = mid - 1
    else:
        start = mid + 1

print(end)