[C/C++ 백준 2225번] 합분해 (Gold 5)

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

2225번: 합분해

문제의 조건에서 '덧셈의 순서가 바뀐 것은 다른 것으로 한다' 라는 조건이 있어, 풀기 어렵진 않은 문제였던 것 같다.

dp[N][K]의 배열을 합이 N, 개수가 K개인 합분해의 경우의 수로 하고, 첫번째 수가 0, 1, 2, ... N일 경우를 생각해서 점화식을 세워보자. 

 dp[i][j]에서 i, j가 0일 때와 j가 1일때 dp[i][j]가 몇일지 초기조건만 세워주면, 그 이후는 쉽다.

 

#include <cstdio>
int main(void){
	int N, K;
	int dp[201][201]={};//dp[N][K] 합, 개수 
	scanf("%d %d",&N, &K);
	for(int i=0; i<=N; i++){
		for(int j=0; j<=K; j++){
			if(j==0)	dp[i][j]=0;
			else if(j==1)	dp[i][j]=1;
			else if(i==0)	dp[i][j]=1;
			else{
				for(int k=0; k<=N; k++){
					if(i-k>=0)
					{
						dp[i][j] += dp[i-k][j-1]; // 점화식
						dp[i][j] = dp[i][j]%1000000000;	
					}
				}
			}
		}
	}
	printf("%d",dp[N][K]);
}