[백준 2225] 합분해 (DP) (C/C++)

#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 1000000000
 
int N, K;
long long dp[210][210];
 
int solve(int sum, int cnt)
{
    if(cnt > K || sum > N)
    {
        return 0;
    }
    
    if(cnt == K && sum == N)
    {
        return 1;
    }
    
    if(dp[sum][cnt] != 0)
    {
        return dp[sum][cnt];
    }
 
    for(int i = 0; i <= N; i++)
    {
        dp[sum][cnt] = (dp[sum][cnt] + solve(sum+i, cnt+1)) % MOD;
    }
    
    return dp[sum][cnt];
}
 
int main(void)
{
//    freopen("B2225_input.txt", "r", stdin);
    
    cin >> N >> K;
    
    cout << solve(0, 0);
    
    return 0;
}