유형정리(이분탐색) - 백준 1789

1789번: 수들의 합 (acmicpc.net)

1789번: 수들의 합

문제

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

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

예제 입력 1 복사

200

예제 출력 1 복사

19

 

 

문제는 위와 같이 굉장히 간단하다. N개를 무한 루프 속에서 계속해서 더해가다가 지정된 S를 넘는 경우 멈춰주면 된다.

이 때 조심할 점이 S>N이 되는 마지막 지점에서 해당 값이 루프에서 나온 값에 포함되어 있으므로 마지막에 print에서 -1을 시켜주어야 한다는 점이다.

 

S = int(input())

n = 0
sum = 0

while True:
    sum += n;
    if sum > S:
        break;
    n = n + 1

print(n-1)

 

이렇게 문제를 상당히 쉽게 해결했다. 이 문제를 이전에 JAVA로도 풀어 본 경험이 있어서 어디서 본 문제라는 느낌은 들었다. JAVA나 C의 경우 type을 정확하게 지정해주어야 하므로 sum을 long 형에 가까운 수로 문제에 나온 것을 보고 뭔가 따로 강제형 변환을 해주어야 하는 것인지 고민하다가 제출을 해 보았더니 깔끔하게 통과가 나왔다.

 

파이썬은 꽤 큰 수 더라도 언어 자체가 커버할 수 있는 모양이다.