[BOJ] 1789번 수들의 합 파이썬

문제

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

입력

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

출력

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

풀이

#dp

처음에 dp배열에 합들의 값을 저장해줬었는데 그렇게 하니 메모리초과가 났다. 그래서 그냥 sum 변수에 값을 저장하는 방식으로 바꿔 풀었다.

가장 많은 개수의 자연수의 합이 되어야 하기 때문에 가장 잘잘하게(?) 합이 구성되어야 한다. 그렇기 때문에 1부터 더해줘야 한다고 생각을 했고, 이렇게 작은 수부터 더했을 때 sum이 S의 이상이 되면 그 인덱스 값을 저장했다.

S와 같은 경우에는 index값이 정답이 되고 S 초과한 경우 딱 초과한 수만큼의 수를 1개 빼주면 되므로 index-1이 정답이 된다.

코드

S = int(input())

index = 0
sum = 0
for i in range(1, S + 1):
    sum+=i
    if sum>=S:
        index=i
        break

if S==sum:
    print(index)
else:
    print(index-1)