2225번 합분해

 기본적인 DP문제.

 

 주어진 예시를 풀어보자

 N=20, K=2 -> 20 + 0, 19 + 1, 18 + 2, ....., 0 + 20 -> 즉, 21개이다. 

 정답을 DP[N][K]라고 할때 우리는 DP[N-0][K-1] + DP[N-1][K-1] + ..... + DP[N-N][K-1]까지 더하면 된다.

 즉, DP[N][K]+=DP[N-정수][K-1] 라는 점화식을 구할 수 있다.

 

#include <iostream>
#define mod 1000000000
#define MAX 201
 
using namespace std;
 
int dp[MAX][MAX];
int N,K;
 
void solved(){
    
    for(int i=0;i<=N;i++){
        dp[i][1]=1;
       // dp[0][i]=1;
    }
    
    for(int j=2;j<=K;j++){
        for(int i=0;i<=N;i++){
            for(int k=0;k<=i;k++){
                dp[i][j]+=dp[i-k][j-1];
                dp[i][j]%=mod;
            }
        }
    }
    
    cout << dp[N][K]%mod << endl;
}
 
int main(){
    cin >> N >> K;
    
    solved();
}