[백준][DP] 합분해

1. 문제 주소

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

2225번: 합분해

2. 문제

0부터 N까지의 정수를 K개 더하여 N이 나오는 경우의 수를 구하는 문제이다.

[K][N]인 경우에 다음과 같은 식이 된다.

$$x_{1}+x_{2}+x_{3}+...+x_{K}=N$$

이것을 다시 써보면

$$x_{1}+x_{2}+x_{3}+...+x_{K-1}+X = N$$

로 나타낼 수 있으며 이 식은 [K-1][N-X] (X <=N)이 된다. 즉

$$[K][N]=\Sigma [K-1][N-X]$$

가 된다. 이 관계식을 이용하여 코드를 작성하면 풀 수 있다.

3. 소스 코드

#include <iostream>
using namespace std;
 
long long dp[201][201];
long long divide = 1000000000;
 
int main() {
    int n;
    int k;
    cin >> n >> k;
 
    dp[0][0] = 1LL;
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            for (int m = 0; m <= j; m++) {
                dp[i][j] += dp[i - 1][j - m];
                dp[i][j] %= divide;
            }
        }
    }
    cout << dp[k][n] << '\n';
    return 0;
}