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

문제 링크: www.acmicpc.net/problem/1789

1789번: 수들의 합

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

서로 다른 N개의 자연수의 합이 S라고 할 때 N을 최댓값으로 하기 위해서는 1부터 작은 수들을 차례대로 더하여 S보다 커질 때보다 1개 적을 때가 N의 최댓값입니다. 예제를 보면 200이 주어졌을 때, 1부터 20까지 더하면 210이 되고 1부터 19까지 더하면 190이 됩니다. 따라서 1부터 18까지 더하고 200까지 모자란 수를 마지막 수로 정하면 19개가 최대가 됩니다.

그렇다면 N의 최댓값은 어디까지일까요? 1부터 N까지의 합은 N*(N+1)/2인데, N이 N*(N+1)/2와 같아질 때는 N이 1일때 뿐이고, N이 커질수록 N*(N+1)/2의 값이 압도적으로 커집니다. 즉, 자연수 N의 최댓값은 항상 S보다 작거나 같습니다.  이를 이용하여 1과 S사이의 수를 이분 탐색하여 O(log(S))의 시간으로 N의 값을 찾을 수 있습니다. 아래는 제가 문제를 해결한 파이썬 코드입니다.

 

import sys
# n을 입력받습니다.
n = int(sys.stdin.readline())
# 답을 담을 변수 answer를 0으로 초기화합니다.
answer = 0
# 답의 최소값인 1을 왼쪽으로 선언합니다.
left = 1
# 답의 최대값인 n을 오른쪽으로 선언합니다.
right = n
# 이분탐색을 시작합니다.
# 왼쪽이 오른쪽보다 커질 때까지 반복합니다.
while left <= right:
    mid = (left + right) // 2
    # 1부터 mid까지의 합이 n보다 작거나 같으면 answer값을 mid로 갱신합니다.
    # 이후에 left값을 mid+1값으로 갱신합니다.
    if mid * (mid + 1) // 2 <= n:
        answer = mid
        left = mid + 1
    # 1부터 mid까지의 합이 n보다 크다면 right값을 mid-1로 갱신합니다.
    else:
        right = mid - 1