[C++] 백준/Gold/2225. 합분해

문제: 합분해 (백준 2225번)

문제 분석

0부터 $N$까지의 정수 $K$개를 더해서 그 합이 $N$이 되는 경우의 수를 구하는 문제다.

이번 문제도 이전 문제와 비슷하게 지문 자체가 참 짧고 간결하고 DP를 사용한 문제이므로 알고리즘도 간결하다.

다이나믹 프로그래밍을 이용한 해결 방법

$dp[i][j]$를 $j$를 만들기 위해 $i$개의 숫자를 사용하는 경우의 수로 정의한다.

1. 초기화: $dp[1][j]$는 1로 초기화한다. (0부터 $j$까지의 합을 1개의 숫자로 나타낼 수 있는 경우의 수는 1이다)
2. 상태 전이: $dp[i][j]$ 는 $dp[i-1][k]$ 의 합이다. 여기서 $k$는 0부터 $j$까지의 값이다. 각 단계에서 현재 숫자를 포함하여 만들 수 있는 경우의 수를 누적한다.

점화식

$dp[i][j] = \Sigma_{k=0}^j dp[i-1][k]$

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<int>> dp(k + 1, vector<int>(n + 1));
    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 l = 0; l <= j; l++) {
                dp[i][j] += dp[i - 1][l];
                dp[i][j] %= 1000000000;
            }
        }
    }
    cout << dp[k][n];
}