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

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

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

1789번: 수들의 합

실버 5

그리디 알고리즘, 수학

---

접근

N개의 자연수의 합이 입력한 값과 같을때, N의 최댓값을 구하는 문제이다.

이때 N개의 자연수는 전부다 다른 값을 가져야 한다.

합을 이루고 있는 자연수들이 최대가 되기 위해서는 값이 작을수록 좋을 것이다.

200을 입력했다면 1+2+3+4+5...로 계속해서 합산을 해주고, 200을 몇번째로 넘어가는지 확인하면 될 것이다.

 

코드

S = int(input())
sum = 0
N = 0
for i in range(1, S+1):
    sum += i
    N += 1
    if sum > S:
        print(N-1)
        break

sum에다가 계속 값을 더하면서, N의 값도 1을 계속해서 더해준다.

만약 sum이 입력한 값보다 커졌을 경우, N-1이 N의 최댓값이 된다.