[python] 1789, 수들의 합

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

1789번: 수들의 합

 

[문제]

서로 다른 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.
      1. s = 1, sub = 3에서 break 되고 나면 (s = 3) - (sub = 2) = (s = 1) 이 되는데,
      2. s = 1은 이미  sub으로 사용되었기 때문에 그대로 카운트에 넣을 수 없음
      3. (s = 4) - (sub = 1)의 단계까지만 카운트하고
      4. 그 결과인 (s = 3) 을 숫자의 조합 중 하나로 포함시켜줌
      5. 최종적으로 4 = 1 + 3 -> 출력값 = 2 가 됨
      6. 이 결과는 3 - 2 + 1 = 2와 동일