수들의 합

수들의 합

아주 간단한 문제인데, 얼마전 피보나치 수열을 비효율적으로 짰던 비슷한 경험이 떠올라서 간단히 정리하기로 했다.

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

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

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

비효율적인 코드

def function(n):
    total = 0
    for i in range(1,n+1):
        total += i
    return total

n = 1

S = int(input())

while function(n) < S:
    n += 1

print(n-1)

팩토리얼을 계산하는 함수를 만들어서 그 함수가 S보다 커질 때까지 반복했는데, for문이 쓸데없이 많이 반복된다. S가 4,294,967,295와 같이 매우 커지면 시간이 오래 걸린다.

다시 짠 코드

n = 1
S = int(input())
total = 0

while total < S:
    total += n
    if total > S:
        break
    n += 1

print(n-1)

굳이 팩토리얼을 계산하는 함수를 만들지 않고, n을 계속 증가시키며, S보다 커질 때까지 total에 계속 더해준다.