[백준] 2225 - 합분해, C++

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

2225번: 합분해

 본 문제는 0 ~ N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 큰 문제를 작은문제로 나누어 해결할 수 있기 때문에 DP문제이고, d[n][k] = d[n-0][k-1] + d[n-1][k-1] + d[n-2][k-1] + ... + d[n-n][k-1] 으로 점화식을 정의 할 수 있다. Bottom-up 방법을 사용하였고, 미지수가 3개이므로 3중 for문을 사용했다. 사실 DP를 풀기전에 완전탐색을 이용하여 해결하려고 하였으나, 재귀를 이용하여 1+2, 2+1을 서로 다른 경우의 수로 계산하기가 조금 껄끄러웠다.

Bottom-up

#include <cstdio>
 
using namespace std;
 
long long d[201][201];
 
int main() {
    const long long Mod = 1000000000LL;
    int n, k;
    scanf("%d %d", &n, &k);
    d[0][0] = 1LL;
    for (int j = 1; j <= k; j++) {
        for (int i = 0; i <= n; i++) {
            for (int x = 0; x <= i; x++) {
                d[i][j] += d[i-x][j-1];
                d[i][j] %= Mod;
            }
        }
    }
    printf("%lld", d[n][k]);
}