[Python] 백준 2225번 - 합분해 (골드5)

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

2225번: 합분해

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 수학
 - 다이나믹 프로그래밍

 

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

DP문제이다. 딱 봐도

 

이런 문제는 나는 일단 예제를 구현해보려고 한다.

 

처음엔 1차원 배열로 DP를 만들어서 해보려 했으나 답이 없었고

 

2차원배열로 n과 k를 두어서 구현해 보았었다.

 

결론부터 말하자면 dp[k][n]으로 구현하면 된다.

 

예제에 있는 n=6 k=4로 구현해 보면 규칙성이 보인다.

 

여기까지 보니 대충 규칙성이 보인다.

 

아 dp[k][n] = dp[k-1][0...n]까지의합이구나.

 

하지만 우리는 이 정도론 믿을 수 없다.

 

좀 더 알아보자.

 

 

이쯤 되면 규칙성은 확실해졌다.

 

나머지를 구해본다면

 

 

이제 구하는 법은 알았다.

 

코드로 구현해 보자.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

dp = [ [0 for _ in range(n+1)] for _ in range(k+1)]

for i in range(n+1):
    dp[1][i] = 1

for i in range(2, k+1):
    for j in range(n+1):
        dp[i][j] = sum(dp[i-1][:j+1]) % 1000000000
        
print(dp[k][n])

끝.