2225_합분해

한참 고민을 하다 점화식을 대충 짤 수 있었다.    

DP[i][j] = DP[i - 0][j - 1] + DP[i - 1][j - 1] + ... + DP[1][j - 1] + 1   

 이런 식이 나왔다.    

이 문제를 풀기 위해 우선, 이차원 배열에 행과 열 자리에 무엇이 들어가는지 이해해야 한다.   

쉽게 말하면, n을 k 갯수만큼의 수를 이용해 만들겠다는 것이다. DP[k만큼의 수를 이용해 만들 수][갯수(k)]   

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

n을 숫자 2개를 이용하여 만들시 n + 1개로 만들 수 있었다. 즉 dp[n][2] = n + 1로 초기화 할 수 있었다.   

for (int i = 0; i <= n; i++)
        dp[i][1] = 1;

다음은 dp[i][1] 일 때는 1이므로 다 1로 초기화 해준다. 

 

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

아까 미리 구상해 놓은 점화식을 적어준다. 이 때 주의할 점은 계산 할 때 나머지 1000000000을 하는 것이다. 이것에 따라 큰 수 일 때는 답이 이상하게 나오므로 이런 세세한 컨트롤를 잘 하는 것이 중요한 것 같다. 

 

전체코드

#include<iostream>
 
using namespace std;
 
int main(void) {
    int n, k;
    int dp[201][201] = { 1 };
 
    cin >> n >> k;
    for (int i = 0; i <= n; i++)
        dp[i][2] = i + 1;
    for (int i = 0; i <= n; i++)
        dp[i][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 3; j <= k; j++) {
            for (int m = 0; m < i; m++)
                dp[i][j] = (dp[i][j] + dp[i - m][j - 1]) % 1000000000;
            dp[i][j] = (dp[i][j] + 1) % 1000000000;
        }
    }
    cout << dp[n][k] % 1000000000 << "\n";
}

결과