71. Python 백준 1789 번 수들의 합 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 수 들의 합 Python 백준 1789번 입니다.

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

1789번: 수들의 합

 

 

N개의 자연수의 합 S가 주어질 때 N의 최대값을 묻는 문제이므로

최대한 작은 수들의 합이 S 가 되면 되겠죠.

1부터 n까지의 합은 n * (n +1)/2 입니다.

3가지의 경우가 있습니다.

1. S보다 1부터 n까지의 합이 작다면  S = n(n+1)/2 을 만족시키지 못하므로 n을 증가시킵니다.

2. S보다 1부터 n까지의 합이 S 와 같다면 n은 S를 만들기 위한 N의 최대값이 되고 

3. S보다 1부터 n까지의 합이 S보다 크다면 (n을 1씩 증가시키면서 n * (n +1)/2 을 만들었을 때)

n * (n -1)/2  이 S보다 작고, n(n+1)/2 가 S 보다 크다는 말과 같고 

첫번째 식에서 n을 더했을 때 S 보다 커지게 되므로

n보다 작고 S = n(n+1)/2 - x  를 만족하는 수 x가 지금까지의 합에 존재한다는 것을 알 수 있습니다.

즉 S가 주어질 때 N의 최대값은 n - 1개가 되죠

위 직관으로 코드를 작성해봅시다.

 

수 들의 합 백준 1789번 파이썬 최종 코드입니다.

S = int(input())
N = 1
while N*(N+1)/2 <= S:
    N += 1
print(N - 1)

S를 입력받고

합의 공식 n(n+1)/2 이 S보다 작거나 같으면 1을 더하고,

합의 공식이 S 보다 크다면

1을 빼서 출력하는 코드입니다.

 

 수 들의 합 백준 1789번 파이썬 풀이 이었습니다. 감사합니다.