[2225] 합분해

문제 링크 : https://www.acmicpc.net/problem/2225

2225 - 합분해

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

숫자를 $K$개 뽑고 아무렇게나 더해서 그 값이 $N$인 경우를 출력하면 되는 문제이다. 다만 골때리는게 같은 수를 여러번 쓸수도 있고 덧셈의 순서가 바뀐 것도 다른 경우로 친다는 것이다. 예를 들어 0, 0, 0, N인 것과 N, 0, 0, 0인 경우를 다르게 쳐야한다는 것이다.

그래서, 숫자 $K$개를 뽑는다는 개념을 쓰는 것은 사실상 힘들다. 그러면 점화식을 세울 수 있는지 확인해봐야한다. $(a, b)$를 ‘합이 a인 수를 b개의 다른 수로 만들 수 있는 경우의 수’ 라고 정한다면 $(a, b) = \sum_{i=1}^{n} {(a - i, b-1)}$로 계산할 수 있다. $(a - x, b- 1)$에 $x$라는 수를 추가하면 그것이 $(a, b)$가 될 수 있기 때문이다.

점화식이 세워질 수 있는 문제면 dp를 이용하여 설계할 수 있다. 시작점은 ‘0을 만들 수 있는 경우의 수’ 와 ‘수 1개로 만들 수 있는 수들의 경우의 수’ 가 될 수 있다. 전부 각각 1가지밖에 존재하지 않는다.

이후는 dp 점화식을 이용하여 dp식을 해결하기만 하면 된다.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 27

#include <stdio.h>

#define MAX_IDX (200 + 1)
int dp[MAX_IDX][MAX_IDX];
int n, k;

const int mod = (int)(1e9);

int main() {
    scanf("%d %d", &n, &k);

    for (int i = 0; i < MAX_IDX; ++i) {
        dp[0][i] = 1;
        dp[i][1] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= k; ++j) {
            for (int a = 0; a <= i; ++a) {
                dp[i][j] += dp[i - a][j - 1], dp[i][j] %= mod;
            }
        }
    }

    printf("%d", dp[n][k]);
    return 0;
}