[백준 c++] 2225 합분해

---

문제

https://www.acmicpc.net/problem/2225
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우).
또한 한 개의 수를 여러 번 쓸 수도 있다.

---

풀이

k개를 더해서 N을 만드는 거니까 dp를 구성할 때
1. 몇 개 더했는지
2. 합이 얼마인지
dp[개수][합] 이렇게 두 가지 정보가 필요하다.

숫자 1개를 쓰는 경우는 각각 1가지 밖에 없다.
dp[1][3]의 경우 숫자 1개를 써서 3를 만드는건데 3를 쓰는 경우 하나다.

숫자 2개를 써서 3을 만드는 dp[2][3]의 경우
(0,3), (1,2), (2,1), (3,0) 이렇게 있는데

결국 다음과 같다.

숫자 1개를 써서 0을 만드는 경우 +
숫자 1개를 써서 1을 만드는 경우 +
숫자 1개를 써서 2을 만드는 경우 +
숫자 1개를 써서 3을 만드는 경우

이걸 이용해서 점화식을 세울 수 있다.
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod

---

코드

#include <iostream>
using namespace std;
int n, k;
long long dp[201][201], mod = 1000000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 0; i <= n; i++)
        dp[1][i] = 1;

    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= j; k++)
            {
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
            }
        }
    }
    cout << dp[k][n] % mod << "\n";
}