[BOJ] 2225 : 합분해

이전의 경우의 수에 N 이하의 값을 더한다고 해보자.

N = 3, K = 2 에서 다음과 같은 경우가 가능하다.

0 + 3

1 + 2

2 + 1

3 + 0

N = 3, K = 3 에서 다음과 같은 경우가 가능하다.

(0+0) + 3

(0+1, 1+0) + 2

(0+2, 1+1, 2+0) + 1

(0+3, 1+2, 2+1, 3+0) + 0

이를 수식으로 표현하면 아래과 같다.

 $$DP[N][K] = \sum_{i=0}^{N} DP[i][K-1]$$

모든 N에 대해서 k=1 일때, 다음이 성립한다.

$$DP[N][1] = 1$$

초기화를 해준 뒤에, 3중 for문으로 각 DP[i][j]의 값을 구한다.

#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000000
int dp[201][201];
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) dp[i][1] = 1;
    
    for (int i = 0; i <= n; i++) {
        for (int j = 2; j <= k; j++) {
            for (int z = 0; z <= i; z++) {
                dp[i][j] += dp[z][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }
 
    cout << dp[n][k];
}