백준 2225 - 합분해

문제

 

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

2225번: 합분해

 

 

풀이

 

d[k][n]을 k개를 이용해 n을 만든다고 가정한다. k개의 원 ○ + ○ + ○ + ... + ● = N 이라고 한다. ●에 올 수 있는 수 i는  0부터 N까지이다. 그러면 다음과 같은 점화식을 만들 수 있다.

d[k][n] = d[k-1][n-i] (i = 0~n)

이 점화식을 이용해 문제를 해결한다.

 

코드

 

#include <iostream>
 
using namespace std;
 
int dp[201][201];
int N, K;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> K;
 
    dp[0][0] = 1;
 
    for (int i=1; i<=K; i++)
    {
        for (int j=0; j<=N; j++)
        {
            for (int k=0; k<=j; k++)
            {
                dp[i][j] += dp[i-1][j-k];
                dp[i][j] %= 1000000000;
            }
        }
    }
 
    cout << dp[K][N];
 
    return 0;
}