2225 합분해

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

[2225번: 합분해

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

www.acmicpc.net](https://www.acmicpc.net/problem/2225)

---

문제가 말하는 대로 합분해를 해보았다.

 

예를 들어서 0부터 6까지의 정수들 중에 2개를 사용해 6을 만든다고 했을 때 다음과 같은 조합이 나온다.

0 6
1 5
2 4
3 3
4 2
5 1
6 0

여기서 더 나아가 0부터 6까지의 정수들 중에 3개를 사용해 6을 만든다고 했을 때, 다음과 같은 조합을 볼 수 있다.

0 0 6
0 1 5
0 2 4
0 3 3
0 4 2
0 5 1
0 6 0
1 0 5
1 1 4
1 2 3
1 3 2
1 4 1
1 5 0
2 0 4
2 1 3
...

근데 살펴보면 바로 직전에 0부터 6까지의 정수들 중 2개를 사용했을 때 만들었던 조합이 보인다.

 

이걸 생각해보면 제일 앞자리의 숫자를 바꿔가면서 조합을 찾을 때 이미 구했던 조합들을 활용해볼 수 있다는 것이다.

 

S(N, K) = 0부터 N까지의 정수들 중 K개를 사용해 N을 만들 수 있는 조합의 수

 

S(N, K)를 위처럼 정리해두어보면 S(6, 3)은 S(6, 2) + S(5, 2) + S(4, 2) ... + S(0, 2) 임이 보인다.

 

제일 앞자리의 숫자를 바꾸면서 재귀식을 돌리면 되는데, 메모이제이션을 통해 연산을 최소화시키면 된다.

#include <iostream>
int dp[201][201]{ 0 };
int S(int n, int k) {
    if (k == 1) {
        return 1;
    }
    if (dp[n][k]) {
        return dp[n][k];
    }
    for (int i = n; i >= 0; i--) {
        dp[n][k] = (dp[n][k] + S(i, k-1)) % 1000000000;
    }
    return dp[n][k];
}
int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    printf("%d", S(N, K));
}