백준 / 다이나믹 프로그래밍 / 2225번 / 합분해 / C++

문제

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

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

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

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

예제 입력 1 

20 2

예제 출력 1 

21

 

#include <iostream>
using namespace std;

const int N = 201;
const int K = 201;
const int divisor = 1e9; 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long dp[K][N] = {0,};	
	int n, k;
	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] %= divisor;
		}
	}
	
	cout << dp[k][n] << '\n';
	
	return 0;
}

---

일단 dp[k][n]는 n을 0부터 n까지의 수중에서 k개의 합으로 나타낼 수 있는 경우를 나타낸다.

n을 수 1개로 나타내는 경우는 무조건 n하나로 나타내는 경우 한가지이기 때문에 dp[1][0...n]을 모두 1로 초기화했다.

 

예시로 dp[2][2]가 있다고 생각해보자.

위의 의미는 0부터 2까지의 수중에서 2개의수로 2를 나타내는 경우의 수이다.

 

0 + 2 = 2

1 + 1 = 2

2 + 0 = 2

 

위와 같을 것이다.

 

우리는 위의 식이 2개의 수로 2를 만든 식이지만, 아래와 같이 다시 나타낼 수 있다.

 

1개의 수로 0을 나타냄 + 1개의 수로 2를 나타냄 = 2

1개의 수로 1을 나타냄  + 1개의 수로 1을 나타냄 = 2

1개의 수로 2를 나타냄 + 1개의 수로 0을 나타냄 = 2

 

위에서 + 연산자 앞의 항만 따로 뽑아서 생각해본다면 다음과 같이 나타낼 수 있다.

 

dp[1][0]

dp[1][1]

dp[1][2]

 

따라서 우리는 위와같은 결과 도출로 일반항을 얻어낼 수 있는데 아래와 같다.

dp[k][n] = dp[k-1][0] + dp[k-1][1] + ... + dp[k-1][n] 이다.

위의 일반항을 코드로 나타내준다면 풀리는 문제이다.