백준 1789번 수들의 합 | python | 그리디

문제

링크

풀이

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값을 구하는 문제이다. 자연수 N이 최대가 되려면 가장 작은 자연수인 1부터 차례대로 더해나가야 한다.

i를 현재까지 더한 자연수의 개수, cur을 현재 값이라고 했을 때
계속 i를 1씩 증가해 cur값에 더하다보면 어느순간 cur값이 s보다 크거나 같아지는 시점이 오게 될 것이다. 그 시점에 while문을 빠져나와 i값을 출력해주면 된다.

참고로 cur값이 s보다 커질 때에는 i가 아닌 i에서 1뺀 값을 출력해야하는데, 이는 cur값이 s보다 커지는 시점이 지금까지 살펴본 서로 다른 자연수들 중에서 하나의 값만 빼면(i-1) s값을 만들수 있다는 뜻이기 때문이다.

이해가 안 간다면 s=11일 때를 생각해보자.

i=1일 때, cur=1 (11 안넘음)
i=2일 때, cur=1+2 (11 안넘음)
i=3일 때, cur=1+2+3 (11 안넘음)
i=4일 때, cur=1+2+3+4 (11 안넘음)
i=5일 때, cur=1+2+3+4+5 (11 넘음 break)

지금까지 cur에 들어간 자연수는 1,2,3,4,5이다. 우리는 여기서 4를 빼면 11을 만들 수 있다는 것을 알 수 있다.

즉, 앞서 말한대로 지금까지 살펴본 서로 다른 자연수들 중에서 하나만 빼면 s값을 만들수 있다고 확신할 수 있다.

11이 아닌 매우 큰 숫자일때에도 무조건 지금까지 다룬 자연수들 중 하나의 값만 빼면 된다. 그 값이 무엇인지는 알 필요가 없다. 단순히 1만 빼주면 되는 것이다 !

import sys

input = sys.stdin.readline

s = int(input())

cur = 0

i = 1
while True:
    cur += i
    if cur > s:
        i = i - 1
        break
    elif cur == s:
        break
    i += 1


print(i)

아주 쉬운 그리디 😎