[algorithm] 백준 - 합분해

이 문제는 DP문제이다.

 

0부터 n까지 k개를 더해서 n이 되는 경우의 수를 구하는 것이며, 덧셈의 순서가 바뀐 경우는 다른 경우로 센다.

그리고 한개의 수를 여러번 쓸 수 있다.

 

n은 2고 k는 2이라고 예를 들어보자.

k	n	n을 구하기 위한 과정
1	0	0 경우의 수 : 1개
1	1	1 경우의 수 : 1개
1	2	2 경우의 수 : 1개
2	0	0 0 경우의 수 : 1개
2	1	0 1 1 0 경우의 수 : 2개
2	2	0 2 1 1 2 0 경우의 수 : 3개

 따라서 3개라는 것을 알 수 있다.

여기서 알아야할 것은 n을 구하기 위해서는 사실

k	n	n을 구하기 위한 과정
1	0	0 경우의 수 : 1개
1	1	1 경우의 수 : 1개
1	2	2 경우의 수 : 1개
2	0	0 0 경우의 수 : 1개
2	1	0 1 1 0 경우의 수 : 2개
2	2	0 2 1 1 2 0 경우의 수 : 3개

주황색으로 표시된 값의 경우의 수만 알아도 된다는 것이다.

즉 dp[i][1] 만 알아도 된다는 것이다.

왜냐하면 구하고자 하는 값 - i 로 설정되기 때문이다. 

 

이것을 점화식으로 표현하면

 

dp[n][k] = dp[n - 1][k - 1] + dp[n - 2][k - 1] + ... + dp[0][k - 1]

 

이렇다.

 

코드로 표현해보면

// 합분해
#include <iostream>
using namespace std;

int main(void){
    int n,k,dp[201][201] = {1};
    cin >> n >> k;
    for(int i = 0; i <= n; i++){
        for(int j = 1; j <= k; j++){
            for(int l = 0; l <= i; l++){
                dp[i][j] = (dp[i][j] + dp[i - l][j - 1]) % 1000000000;
            }
        }
    }
    cout << dp[n][k] % 1000000000;
}