[BOJ 2225] 합분해

- 문제 요약

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다. (1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

(1<=N<=200, 1 <=K<=200)

 

 

- 알고리즘 정리

 

DP 문제입니다.

 

dp[K][N] = X (K개를 더해서 N을 만들 수 있는 경우의 수가 X)

dp[K][N] = dp[K-1][0] + dp[K-1][1] + ... + dp[K-1][N]

 

위와 같이 점화식을 작성하면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

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

#define MAX 201
typedef long long ll;
ll n,k,dp[MAX][MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	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++){
			for(int l=0;l<=j;l++){
				dp[i][j]+=dp[i-1][l];
			}
			dp[i][j]%=1000000000;
		}
	}
	cout<<dp[k][n];
}

코드 제출 결과