백준 2225합분해

algorithm : DP

 

해설 

DP[i][j] = i개의 정수를 더하여 j를 만들수 있는 경우의수 

6 3의 경우 이런식으로 표가 채워진다

1	1	1	1	1	1
1	2	3	4	5	6
1	3	6	10	15	21

 

위쪽에서 오는 경우와 옆에서 오는 경우를 더한다음 MOD로 나누면서 dp 테이블을 채우고 dp[K][N]을 출력하면된다

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
#define MOD 1000000000
using LL = long long;
using namespace std;

int N,K;
int dp[LM][LM];

void input(){
    scanf("%d %d",&N,&K);
}

void DP(){
    for(int i = 0 ; i <= N ; i++) dp[1][i] = 1;
    for(int i = 2 ; i <= K ; i++){
        for(int j = 0 ; j <= N ; j++){
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }
    printf("%d",dp[K][N]);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}