수들의 합 - 1789

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	23402	9919	8396	43.298%

문제

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

입력

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

출력

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

예제 입력 1

200

예제 출력 1

19

 

Solution

https://github.com/anothel/BOJ/blob/main/python/1789_Add_of_numbers.py

GitHub - anothel/BOJ

 

후기

나름 동적 계획법으로 풀었다고 생각한다. 수를 더할 텐데 앞에서부터 많이 더하는 게 많이 더할 것이고, 이분법으로 계속해서 나눠가는 알고리즘을 만들어봤다. 재귀로 푼다고 해도 풀 수 있을 것 같지만 그렇게까지 할 필요는 없을 것 같고 그냥 반복문 선에서 끝냈다. 좀 더 멋지게 만들 방법은 없었을까 고민해본다.

 

(url: https://www.acmicpc.net/problem/1789)