[Python] 백준/BOJ - 1789번: 수들의 합

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

1789번: 수들의 합

 

문제

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

 

입력

S(1 <= S <= 4294967295)

 

출력

자연수 N의 최댓값

 

예제 입력 1

200

 

예제 출력 1

19

 

풀이

최대한 많은 서로 다른 수를 이용해 그 합들이 S가 되게 하기 위해서는 1부터 더해가는 것이 좋다. 예를 들어 S가 7일 때 1+2+3+1=7일 때가 N이 최대가 될 수 있다. 하지만 1이 중복되었으므로 1+2+4=7로 N=3일 때 최대이다.

이렇게 생각하면 복잡하다고 생각할 수 있지만 1+2+...+n의 합이 S를 넘지 않는다는 것만 이용하면 N의 갯수를 구하는 것은 간단하다. 위의 예시에서도 1+2+3=6이지만 n=3일 때까지의 합이 S를 초과하지 않는 다는 것을 알 수 있다. 따라서 n까지의 합이 S보다 작고, 가장 근접할 때 N이 최대가 된다는 것을 알 수 있다. 

 

1+2+...+n까지의 합이 n*(n+1)/2인 것을 이용하면 간단히 해결할 수 있다.

num = int(input())

n = 0
while n * (n + 1) / 2 <= num:
    n += 1
print(n - 1)

간단히 위와 같이 구현해보았다. n*(n+1)/2의 값이 S값보다 작거나 같을 경우 n의 값을 1씩 증가시키며 비교한다. 이 때 n을 1 증가시켰는데 계산 값이 S보다 커지면 while문이 끝나기 때문에 print할때는 n-1을 출력해주면 된다.