백준 2225번 합분해 (C++)

2225번: 합분해

생각을 많이 해야 했던 dp 문제이다. 0부터 N까지 중 정수 K개의 합이 N이 되는 경우의 수를 구해야 한다. 중요한 점은 순서가 다르거나 중복되는 수를 사용해도 다른 경우로 샌다는 점이다. dp[K][N] = 경우의 수로 dp를 구성하였다. 예를 들어 N=3, K=2라고 하면 경우의 수는 (0 + 3), (1 + 2), (2 + 1), (3 + 0)이 된다. 이는 마지막에 더하는 수가 3이면 1개로 0을 만드는 경우가 나올테고, 마지막에 더하는 수가 2이면 2개로 1을 만드는 경우가 나올테고, 마지막에 더하는 수가 1이면 2개로 2를 만드는 경우가 나올 것 이다.
즉 dp[K][N] = dp[K-1][0] + dp[K-1][1] + ... + dp[K-1][N]이 된다.
생각보다 어려웠던 문제였다.

#include <iostream>

using namespace std;

int N, K;
long long dp[201][201];

void solution() {
    for (int i = 0; i <= N; i++) {
        dp[1][i] = 1;
    }

    for (int i = 2; i <= K; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
            dp[i][j] %= 1000000000;
        }
    }

    cout << dp[K][N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;

    solution();

    return 0;
}