[BOJ]1789. 수들의 합

문제:

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

 

입력:

첫째 줄에 자연수 S(1<=S<=4294967295)가 주어진다.

 

출력:

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

 

풀이방법:

최대한 많은 서로 다른 수를 사용하며 그 합들이 S가 되도록 만들기 위해서는 1부터 차례대로 값을 더하는 것이 가장 많이 사용할 수 있다. 즉 예를 들어 11을 만들기 위해서는 1+2+3+4+1=11과 같이 사용하는 것이 N이 최대가 된다. 하지만 1을 중복해서 사용했다. 그래서 이 1을 4에다가 붙여서 다음과 같이 식을 구성하고 이 것이 최댓값이 되게 된다. (1+2+3+5=11)

 따라서 S를 알 때, 자연수 N의 최댓값을 구하기 위해서 일반화를 할 수 있다. 1+2+ .... + n의 합은 S를 넘지 않는다. 즉 1+2+ .... + n +a =S가 되게 되는 것이다. 이 a를 항상 n에 붙임으로써 N의 최댓값을 구할 수 있다. 즉 1부터 n까지의 합이 S와 근접할 때 N의 최댓값이 된다.

 1+2 + .... + n = ((n+1)*n)/2 이므로 이를 활용해서 m을 추정할 수 있고 이 값을 하나씩 감소시키며 n을 찾을 수 있다.

import math
s=int(input())
m=int(math.sqrt(2*s))
while m*m+m>2*s:
    m-=1
print(m)

문제링크:

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