[백준] 1789번 수들의 합(feat. 그리디, 수학)

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

문제 분석

• 첫 번째 단계(문제 요약 및 조건 파악)

서로 다른 N개의 자연수의 합을 S라고 한다.
S가 주어졌을 때, N의 최댓값은 얼마인지 구해야 한다.

입력으로는 자연수 S(1 <= S <= 4,294,967,295)가 주어진다.

 

• 두 번째 단계 (문제 핵심 파악하기)

S를 만드는 서로다른 자연수들의 갯수 N을 크게하려면, 
가능한 가장 작은수부터 더해야 할 것이다.

s = 10을 생각해보자

1 + 2 + 3 + 4 + 5  = 15이다.
이때, 4만 빼주면, 합은 10이 되고, N이 4개로 최댓값이 된다.

s = 50

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 이다.
이때, 5만 빼주면, 합은 50이 되고, N은 9개로 최댓값이 된다.

이 로직을 이용하여 코드를 작성하면 될 것이다.

'''
서로 다른 N개의 자연수의 합이 S라고 한다.
S를 알 때, 자연수 N의 최대값을 구해야 한다.

잘 생각해 보면,
최대한 작은 수를 더해서 S를 만들어야지만 N이 최대가 될 수 있다

n까지 1부터 더해가다가 n보다 큰 값이 나오면, 그 직전의 수가 문제의 정답

S = 10
1
sum 1
result 1
2
sum 3
result 2
3
sum 6
result 3
4
sum 10
result 4
5
sum 15
result 5
'''

 

코드 작성

import sys

n = int(sys.stdin.readline().rstrip())
sum = 0
result = 0

for i in range(1, n + 1):
    sum = sum + i
    result = i
    if sum > n:
        result = result - 1
        break

print(result)