[BAE/<JOON> 문제풀이] 2225. 합분해 (DP.034)

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

2225번: 합분해

문제 난이도 정말 잘 나뉘여져 있는 것 같다. 골드 5까지만 정확하게 할만하고 그 이상은 무조건 이틀 이상 걸린다.

 

 

 

 

k값을 점화식에 어떻게 넣느냐가 헷갈리는 문제였다. 2가지 사항을 고려하며 풀 수 있다.

 

1. 0을 만들 수 있는 가짓수

 

2. [만들 숫자]와, [그 숫자를 만들기 위해 사용할 숫자의 갯수]

 

두가지이다. 

 

이 두가지를 고려하며 아래항부터 계산하여 답을 구할 수 있다.

 

첫째, 숫자를 몇개를 사용하든 0을 만드는 경우의 수는 무조건 1가지이다. 덧셈의 순서를 고려하지 않더라도 0을 만들려면 0면 써야하기 때문이다.

 

둘째, 숫자 3개를 사용하여 10을 만드는 경우의 수는

 

숫자 2개를 사용하여 10 이하의 숫자를 만들었던 경우의 수 를 모두 합친 것과 같다.

 

마찬가지로 숫자 2개를 사용하여 10 이하의 숫자를 만들었던 경우의 수를 구하기 위해서

 

숫자 1개로 10 이하의 숫자를 만들었던 경우의 수들을 구한다.

 

 

위 내용을 코드로 표현하면 다음과 같다.

 

n = 만들려는 숫자
k = 사용하는 숫자의 갯수
dp[n][k] = n을 만들기 위해 k개의 숫자를 쓴 경우의 수

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

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    using ull = unsigned long long;
    int n, k;
    cin >> n >> k;
    vector<vector<ull>> dp;
    dp.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        dp[i].resize(k + 1);
    }
    for (int i = 0; i <= n; i++) {
        dp[i][1] = 1;            
    }
    for (int i = 1; i <= k; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = i; l >= 0; l--) {
                dp[i][j] += (dp[i - l][j - 1]);
                dp[i][j] %= 1000000000;
            }
        }
    }

    /*for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/

    cout << dp[n][k];
    return 0;
}