2225 - 합분해

//2225 - 합분해
 
#include <iostream>
using namespace std;
 
#define MOD 1000000000
 
int N, K;
int cache[201][201];
 
void init()
{
    cin >> N >> K;
    for(int i = 0; i<=N; ++i)
        for(int j = 0; j<=K; ++j)
            cache[i][j] = -1;
}
 
int dp(int cost, int k)
{
    if(cost < 0) return 0;
    if(k < 0) return 0;
    if(!k && !cost) return 1;
    int& ret = cache[cost][k];
    if(ret != -1)
        return ret;
    ret = 0;
    for(int i = 0; i<=N; ++i)
    {
        ret += dp(cost - i, k-1);
        ret %= MOD;
    }
    return ret;
}
 
int main()
{
    init();
    cout << dp(N, K);
}

 

 

 

 

 

 

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

2225번: 합분해

 

 

 

 

 

 

합분해

dp문제

C(cost, k) : k번째에 cost를 만들수 있는 경우의 수