ACMICPC 1789 수들의 합

문제

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

입력

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

출력

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

한 5초동안 뭐징.... 했는데 생각해보니 쉬운 문제.

N개의 자연수의 합으로 S를 표현하고 싶은데 N이 최대값이 되어야한다.

그렇다면 뭐...1~N-1까지 더한 후 남은 값을 더해주는게 

최대 N개의 자연수의 합으로 S를 나타내는 방법 아닐까.

S = 1+2+3+....+N-1+a

그럼 이제 남은 것은 이때의 N 값을 구하기만 하면 된다.

1~N까지의 합 공식이 N(N+1)/2 이니,

N(N+1) <= 2S

여기서 살짝 고민했는데, N^2+N은 N의 값이 커짐에 따라 N^2와 근사치를

나타내니까...루트2S를 구해서 이 값을 N이라 두고 N(N+1) <= 2S 수식을

만족할때까지 N 값을 1씩 낮춰주었다.

설명하는 것보다 코드를 보는게 더 이해가 빠를지도...

#1789 수들의 합 #N까지의 합 : (N+1)*N/2 #(N+1)*N/2 <= S S = int(input()); #N(N+1) <= 2S 를 만족하는 N의 최대값 N = int((2*S)**0.5); while (N*N+N > 2*S): N -= 1; print (N);

문제집 : https://www.acmicpc.net/workbook/view/4