합분해

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

2225번: 합분해

1,2,3 더하기와 유사..

d[k][n] = 시그마 d[k-1][n- L]  ( 0 <= L <= n )

시간 복잡도 O(( K * N) * N) --> 3중 for 문

#include <iostream>
 
using namespace std;
long long d[201][201];
long long mod = 1000000000;
 
int main()
{
    int n, k;
    cin >> n >> k;
 
    d[0][0] = 1LL;
 
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int l = 0; l <= j; l++)
            {
                d[i][j] += d[i - 1][j - l];
                d[i][j] %= mod;
            }
        }
    }
 
    cout << d[k][n] << '\n';
 
    return 0;
}