3장 다이나믹 프로그래밍 - (5) 문제 풀이 4 [2225번 - 합분해]

1. 문제 

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

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

2. 입력

두 정수 N(1<=N<=200), K(1<=K<=200) 

3. 출력

답을 1,000,00,000으로 나눈 나머지를 출력

4. 정답

d[n][k] : k개로 n을 만드는 경우의 수

d[n][k] = d[0][k-1] + d[1][k-1] + d[2][k-1] + ... + d[n][k-1] 

#include <iostream>

using namespace std;

long long d[201][201];

int main(void) {

int n, k;

cin >> n >> k;

// d[n][1] = 1

for (int i = 0; i <= 200; i++) {

d[i][1] = 1;

}

for (int i = 1; i <= 200; i++) {

d[0][i] = 1;

}

for (int i = 1; i <= n; i++) {

for (int j = 2; j <= k - 1; j++) {

for (int k = 0; k <= i; k++) {

d[i][j] += d[i - k][j-1];

d[i][j] %= 1000000000;

}

}

}

for (int i = 0; i <= n; i++) {

d[n][k] += d[n - i][k - 1];

d[n][k] %= 1000000000;

}

cout << d[n][k] << endl;

return 0;

}