[BOJ] 백준 1789번 - 수들의 합 (Python)

문제

문제 바로가기

해결

딱 봐도 작은 자연수부터 더하는 그리디 알고리즘인 것을 눈치챘다.

우선 예제인 200을 1부터 차근차근 더하다보니 1 + 2 + 3 + 4 + ... + 19임을 알았고 그럼 201은 어떨까 생각해보면 1 + 2 + 3 + 4 + ... + 19과 동일하지만 마지막만 19가 아니라 20이 될 것이라고 생각했다.

그럼 출력 결과가 19가 아니라 20이 되려면 어떻게 해야 할까. 20이 결과가 되기 위해선 19로 차근차근 다 빼도 20 이상의 수가 남았을 경우인 220이상이 될 것이고, 이는 21을 또 빼도 되기 전인 241 전까지가 될 것이다.

여기까지만 생각하면 접근법은 이미 나왔고 코드로 작성하는 것은 매우 쉬워진다. 그냥 1부터 나누는 수를 증가시켜나가며 S를 나누고, S를 나눈 몫이 1 이상일 경우, 즉 나눌 수 있을 경우 S에서 divid를 빼주며 반복문을 실행해주고, 몫을 낼 수 없을 때까지 반복해주면 된다.

파이썬으로 작성한 코드는 다음과 같다.

S = int(input())
cnt = 0
divid = 1
while S / divid >= 1:
  S -= divid
  cnt += 1
  divid += 1
print(cnt)