[C++][BOJ-2225(합분해)]

백준 합분해(2225)

풀이

K ＼ N	0	1	2	3	4
0	0	0	0	0	0
1	1	1	1	1	1
2	1	2	3	4
3	1	3	6
4	1	4	10
5	1	5	15

 

점화식 

D[K][N] = D[K][N-1] + D[N-1][N]

 

소스 코드

#include <bits/stdc++.h>
#define Moduler 1000000000
using namespace std;

int main (){
	int K,N;
	long long dp[201][201]={0,}; // k n
	scanf("%d %d",&N,&K);
	for(int i = 0; i<=200; i++){
		dp[i][0] = 1;
	}

	for(int k = 1 ; k <= K ;k++){
		for(int n = 1; n <=N ; n++){
			dp[k][n] = (dp[k][n-1] + dp[k-1][n])%Moduler;	
		}
	}	
	printf("%lld",dp[K][N]);
	return 0;
}