합분해 2225

문제

접근 방법

N, 1인 경우 1개 (N이 1개)
0, N인 경우 1개 (0이 N개만큼)

1, 2인 경우 1+0, 0+1
1, 3인 경우 1+0+0, 0+1+0, 0+0+1
1, 4인 경우 1+0+0+0, 0+1+0+0, 0+0+1+0, 0+0+0+1
1, N인 경우 N개

2, 2인 경우 [2+0], 0+2, 1+1
2, 3인 경우 [2+0+0, 0+2+0, 1+1+0], 1+0+1, 0+1+1, 0+0+2
2, 4인 경우 [2, 3인 경우에 0만 붙은 경우], [1, 3인 경우에 1을 더한 경우]

즉 (N, M)인 경우는 (N, M-1)인 경우+(N-1, M)인 경우이다.

코드

#include <iostream>
#include <vector>
typedef unsigned long long ull;
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<vector<ull>> dp(N + 1, vector<ull>(K + 1, 1));
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 2; j <= K; ++j)
        {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
        }
    }
    cout << dp[N][K];
}

풀이

DP문제답게 규칙을 찾아내어서 적용하면 된다.