2225 합분해

2225. 합분해 / c++ / Gold5 / 12분

문제

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

1. 0~N까지의 정수 K개를 더해 합이 N이 되는 경우의 수를 1’000’000’000으로 나눈 값을 출력

접근 방식

동적 프로그래밍

1. dp[n][k] = for (i = 0 ~ n) dp[n][k] += dp[n-i][1] + dp[i][k-1]

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#define MOD 1'000'000'000
using namespace std;

int N, K;
unsigned long long dp[201][201] = {};

unsigned long long DP(int n, int k)
{
    if (k == 1 || n == 0) return 1;
    if (dp[n][k] == 0)
    {
        for (int i = 0; i <= n; ++i)
        {
            dp[n][k] += DP(n - i, 1) * DP(i, k - 1);
            dp[n][k] %= MOD;
        }
    }

    return dp[n][k];
}

int main()
{

    cin >> N >> K;

    cout << DP(N, K) << '\n';

    return 0;
}

다시 생각해 볼 점

1. 이번 dp는 dp[i][j] = dp[i-k][j-1] + d[k][1] 의 형태였다.
2. 즉 3번 더해 12를 만들려면
   1. 1번 더해 12를 만드는 경우 * 2번 더해 0을 만드는 경우 부터
   2. 1번 더해 0을 만드는 경우 * 2번 더해 12를 만드는 경우 까지

   다 더하면 된다.