백준 #1789

수들의 합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

2 초

128 MB

23608

10006

8474

43.299%

문제

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

입력

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

출력

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

예제 입력 1 복사

200

예제 출력 1 복사

19

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: newton08, upple1

알고리즘 분류

• 수학
• 그리디 알고리즘

 

 

 

 

---

import sys

if __name__ == '__main__':

    N = int(sys.stdin.readline())
    
    i = 0
    total = 0
    while True:
        i += 1
        total += i
        if total > N:
            print(i-1)
            break

만약에 자연수 합이 12라고 하면 1+2+3+4까지 오면 10이고 다음에 +5를 하면 15가 되버린다. 따라서 아래와 같은 식이 성립하므로 숫자를 초과하면 1을 빼준 뒤 출력하면 된다.

 

4 <= 자연수 개수 <5