[BOJ] 이분 탐색 - 1789 수들의 합

www.acmicpc.net/problem/1789

1789번: 수들의 합

 

import sys

x = int(sys.stdin.readline().rstrip())


def total(n):
    return n * (n + 1) // 2


# 최댓값을 만들어야 하니 1부터 더해야 한다.
# 1부터 n까지의 합이 작거나 같고 n + 1의 합은 큰 경우를 만족하는 n을 구한다.
# n까지의 합이 작을 경우 부족한 부분은 다음 수를 추가 후 기존의 수를 제거하는 방식으로 만들 수 있다.
# 예시)
# x = 200
# 1 ~ 19 -> 190 이다.
# 1 ~ 20 -> 210 이다.
# 190에서 부족한 10을 채우기 위해 20을 추가하고 기존의 더했던 10을 뺀다. (수의 개수는 동일)
# 1, 2, 3, ... 9, 11, 12 ... 20으로 200을 만들 수 있다.
def binary_search(target, start, end):
    result = 0

    while start <= end:
        mid = (start + end) // 2

        if total(mid) > target:
            end = mid - 1
        else:
            start = mid + 1
            result = mid
        
    return result


print(binary_search(x, 0, x))