알고리즘 - 백준 2225 (합분해)

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

2225번: 합분해

 

---

 

문제

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

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

 

입력

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

 

출력

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

 

---

 

풀이 및 코드

점화식을 구한 방법은 다음과 같다.

다른 dp 문제들과 비슷하게 표를 그려봤다.

문제에서 제공하는 두번째 입력에 대해 생각해보면,

6을 먼저 두 수의 합으로 나눈다. 0 + 6, 1 + 5, 2 + 4, 3 + 3, 4 + 2, 5 + 1, 6 + 0으로 7개가 나오는데, 각각에 대해 dp 테이블을 채우는 방식으로 구현하였다.

k = 1	1
k = 2	0 + 6	1 + 5	2 + 4	3 + 3	4 + 2	5 + 1	6 + 0
k = 3	7	6	5	4	3	2	1
k = 4	7 + (6 + ... + 1)	6 + (5 + ... + 1)	5 + (4 + ... + 1)	4 + (3 + ... + 1)	3 + (2 + 1)	2 + 1	1
k = 5	...	...	1 + (2 + 1) + (3 + 2 + 1) + (4 + 3 + 2 + 1) + (5 + 4 +... + 1)	1 + (2 + 1) + (3 + 2 + 1) + (4 + 3 + 2 + 1)	1 + (2 + 1) + (3 + 2 + 1)	1 + (2 + 1)	1

이런 식으로 표가 채워지게 된다.

이를 일반화하여 나타내면, 

for(int i = 0; i < k - 2; i++){
    for(int j = n - 1; j >= 0; j--){
        dp[j] = dp[j] + dp[j + 1];
    }
}

으로 나타낼 수 있다.

 

2차원 배열을 사용할 수도 있지만 1차원으로 풀었다.

최종 코드는 다음과 같다.

#include <iostream>

using namespace std;

long long dp[201];
int main(){
    int n, k;
    cin >> n >> k;

    // 1
    if(k == 1){
        cout << 1;
        return 0;
    }

    // 2
    for(int i = 0; i < n + 1; i++){
        dp[i] = 1;
    }

    // 3 ~ k
    for(int i = 0; i < k - 2; i++){
        for(int j = n - 1; j >= 0; j--){
            dp[j] = dp[j] % 1000000000 + dp[j + 1] % 1000000000;
        }
    }

    long long result = 0;
    for(int i = 0; i < n + 1; i++){
        result += dp[i] % 1000000000;
    }

    cout << result % 1000000000;

    return 0;
}

 

https://github.com/haram1117/AlgorithmStudy/commit/f2c2846206f33564aea73b02876b8f3d1be4ad64

DP2225 · haram1117/AlgorithmStudy@f2c2846