728x90
문제
1789번: 수들의 합
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
www.acmicpc.net
코드
i=0
S=int(input())
while S>0:
S=S-i
i+=1
if (S-i)<0:
break
print(i-1)
풀이
서로 다른 N개의 자연수의 합이 입력값 S라고 할때 N의 최대값을 출력하는 문제이다.
이 문제에서 N의 최대값을 구하려면 1부터 n까지의 합을 생각해서 풀면 쉽게 풀 수 있다.
자연수 중 가장 낮은 수인 1부터 1씩 증가한 값을 더한 값이 N의 최대값이다.
만약 S가 55라고 할 때 55는 1부터 10까지의 합을 뜻하며 가장 작은 수부터 더하기때문에 10이 N의 최대값이라고 할 수 있다.
여기서 55(1+2+3+...+10에서 11을 더한 66부터는 N의 최대값이 11이 된다.
즉 55<=S<66 까지 S의 최대값은 10이라고 볼 수 있다.
이런 규칙을 활용해서
입력값 S에서 i값을 1씩 증가시키면서 빼고 S가 음수가 되기 직전 i값에서 1을 빼는 식의 풀이를 활용하면 답을 찾을 수 있다.
'PS' 카테고리의 다른 글
[백준] 1929번 : 소수 구하기(에라토스테네스의 체)- 파이썬[Python] (0) | 2022.01.04 |
---|---|
[백준] 1002번 : 터렛(두 원의 위치 관계)- 파이썬[Python] (0) | 2022.01.04 |
[백준] 1316번 : 그룹 단어 체커- 파이썬[Python] (0) | 2022.01.03 |
[백준] 1934번 : 최소공배수(유클리드 호제법)- 파이썬[Python] (0) | 2021.12.29 |
[백준] 11653번 : 소인수분해 - 파이썬[Python] (0) | 2021.12.29 |
댓글