[백준] 1789 수들의 합 - 파이썬

문제

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

---

풀이

시간을 재고 빠르게 풀 수 있는지 점검하는 문제라길래 대충 시간을 재봤다.

10분정도 걸린 것 같다.

 

S를 이룰 수 있는 서로 다른 자연수의 최대 개수를 구하는 문제이기 때문에 그리디로 풀었다.

작은 수를 쓸수록 N이 커질 것이기 때문이다.

s = int(input())

num = 0
n = 0
while True:
    n += 1
    if s - n >= n + 1: #이 조건을 통과하지 못하면 마지막 수 하나만을 더해서 S를 완성함
        num += 1
        s -= n
    if s - n == 0:
        print(num+1)
        break