백준 문제 풀이 - 수들의 합 1789번

📜 문제 이해하기

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

💡 문제 재정의

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

✏️ 계획 수립

이분탐색으로 문제를 해결할 수 있다. 1부터 mid까지 더한 후 이 값이 s보다 크다면 end를 mid - 1로 이동한다. 만약에 s보다 작다면 start를 mid + 1로 이동한다. 위 내용을 start가 end보다 커질때까지 반복하면 값이 나온다.

💻 계획 수행

if __name__ == '__main__':
    start = 1
    N = int(input())
    end = N
    result = 0

    while start <= end:
        mid = (start+end) // 2
        if N < ((mid * (mid + 1)) / 2):
            end = mid - 1
        else:
            result = mid
            start = mid + 1

    print(result)

🤔 회고

사실 이 문제는 1부터 차근차근 더해가면서 마지막 값을 정해주면 풀 수 있는 문제지만 이분 탐색으로 문제를 풀어보았다.