코딩테스트_python
[python] 1789, 수들의 합
여뉴누
2023. 7. 31. 15:29
728x90
https://www.acmicpc.net/problem/1789
1789번: 수들의 합
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
www.acmicpc.net
[문제]
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
[입력]
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
[출력]
첫째 줄에 자연수 N의 최댓값을 출력한다.
[예제]
[풀이]
s = int(input())
sub = 1
while s >= sub:
s -= sub
sub += 1
print(sub - 1)
- 변수 생성
- s : 입력받은 자연수
- sub : 뺄셈에 사용할 자연수 / 카운트 용도로도 사용
- => s - sub 형태로 연산에 사용
- 풀이
- s >= sub이어야 연산이 가능하기 때문에 while문 조건으로 설정
- break 될 당시의 s, sub 값은 아예 식이 성립조차되지 않는 식이기 때문에 sub - 1을 먼저 해주고
- break 되기 이전 s, sub 값의 경우 s = 0으로 남아야 하는데 이전 식을 그대로 실행하여 s - sub을 해주면 다시 break되는 결과가 남으므로 s를 숫자의 조합 중 하나로 그대로 포함시켜 주면 됨
- sub는 뺄셈의 횟수를 나타내기도 하기 때문에 sub - 2(break 되기 두단계 앞의 값으로 돌아감) + 1(s를 숫자의 조합 중 하나로 포함)
- 결과적으로 sub - 1이 되는 것
- Ex.
- s = 1, sub = 3에서 break 되고 나면 (s = 3) - (sub = 2) = (s = 1) 이 되는데,
- s = 1은 이미 sub으로 사용되었기 때문에 그대로 카운트에 넣을 수 없음
- (s = 4) - (sub = 1)의 단계까지만 카운트하고
- 그 결과인 (s = 3) 을 숫자의 조합 중 하나로 포함시켜줌
- 최종적으로 4 = 1 + 3 -> 출력값 = 2 가 됨
- 이 결과는 3 - 2 + 1 = 2와 동일
- Ex.
728x90