문제
https://www.acmicpc.net/problem/1789
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
출력
첫째 줄에 자연수 N의 최댓값을 출력한다.
예제 입력 1
200
예제 출력 1
19
풀이
아이디어
사실 문제만 봐서는 감이 안오는데, 예제 입력을 보면 서로 다른 자연수의 합이 200일 때, 가장 큰 서로 다른 자연수가 19개다. 자연수의 개수가 최대가 되게 하려면 가장 작은 수부터 더하면 되지 않았을까? 1부터 차례대로 빼면서 개수를 카운팅해 주면 되겠다.
1부터 뺐을 때 마지막에 앞에 나온 수들이 나오지 않는지만 점검해 주면 되겠다.
예를 들어, S = 22이라고 했을 때 22-1, 21-2, 19-3, 16-4, 12-5, 7-6하면 1이 남는다. 1이 앞에 1과 겹치지 않나? 생각했지만 이 남은 1을 뒤에서부터 더해준다고 생각하면 전체 개수에는 영향을 미치지 않는다. 또 200을 생각해보면 1,2,3,4,5,6,...19 까지 빼면 200 - 190이니까 10이 남는다. 이때 남은 10을 서로 다른 19개의 수 중 10개의 수에 1씩 나눠준다고 생각하면 전체 개수에는 영향을 미치지 않는다.
정리하자면, 1부터 순차적으로 수를 증가시키며 빼주고 마지막에 남은 수를 지금까지 뺀 수들에 1씩 더해준다고 생각하면 전체 N의 개수를 구할 수 있다. 이는 코드를 짤 때에는 제일 큰 숫자보다 subNum이 작아지면 이후의 S에 남은 수들은 버리면 된다.
코드
S = int(input())
subNum = 1
count = 0
while (S >= subNum): # 여기 부분에서 등호를 안넣어줘서 한번 틀렸다.
# S=15 라 가정면 S=9일때 subNum =4까지 빼고 S가 5고
# subNum도 5일때 한번 더 빼줘야 한다.!!
# 15 : 15-1, 14-2,12-3,9-4, 5
S = S - subNum
count += 1
subNum += 1
print(count)
짜란
