문제:
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력:
첫째 줄에 자연수 S(1<=S<=4294967295)가 주어진다.
출력:
첫째 줄에 자연수 N의 최댓값을 출력한다.
풀이방법:
최대한 많은 서로 다른 수를 사용하며 그 합들이 S가 되도록 만들기 위해서는 1부터 차례대로 값을 더하는 것이 가장 많이 사용할 수 있다. 즉 예를 들어 11을 만들기 위해서는 1+2+3+4+1=11과 같이 사용하는 것이 N이 최대가 된다. 하지만 1을 중복해서 사용했다. 그래서 이 1을 4에다가 붙여서 다음과 같이 식을 구성하고 이 것이 최댓값이 되게 된다. (1+2+3+5=11)
따라서 S를 알 때, 자연수 N의 최댓값을 구하기 위해서 일반화를 할 수 있다. 1+2+ .... + n의 합은 S를 넘지 않는다. 즉 1+2+ .... + n +a =S가 되게 되는 것이다. 이 a를 항상 n에 붙임으로써 N의 최댓값을 구할 수 있다. 즉 1부터 n까지의 합이 S와 근접할 때 N의 최댓값이 된다.
1+2 + .... + n = ((n+1)*n)/2 이므로 이를 활용해서 m을 추정할 수 있고 이 값을 하나씩 감소시키며 n을 찾을 수 있다.
|
1
2
3
4
5
6
|
import math
s=int(input())
m=int(math.sqrt(2*s))
while m*m+m>2*s:
m-=1
print(m)
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1357. 뒤집힌 덧셈 (0) | 2019.10.08 |
|---|---|
| [BOJ]1629. 곱셈 (0) | 2019.10.07 |
| [BOJ]1075. 나누기 (0) | 2019.10.05 |
| [BOJ]1890. 점프 (0) | 2019.10.04 |
| [Programmers]2017 Kakao.다트 게임 (0) | 2019.10.02 |