[C++ / 백준 2225번] 합분해

 

 

음... 초반 경우의 수를 찾아 규칙을 통해 점화식을 세웠는데, 점화식은 세워서 정답을 맞췄지만 왜 그 점화식이 도출되는지는 모르는 사태가 발생했다. 
   따라서 GPT 에게 도움을 요청했다.

 

경우의 수는 두 가지로 나눌 수 있었는데,

• dp[i-1][j]: 숫자 i-1을 j개의 숫자로 표현한 후, 마지막 숫자에 1을 더하는 경우.
• dp[i][j-1]: 숫자 i를 j-1개의 숫자 합으로 표현한 후, 마지막 숫자에 1을 더하는 경우.

이렇다고 한다.

 

i = 3, j = 2 일때를 예시로 들자.

 

dp[2][2] = (02 20 11)  = 3

dp[3][1] = (3) = 1

dp[3][2] = (03 30 12 21 ) = 4

 

인데 

 

dp[2][2]  에 i를 1 늘리는 경우

 

1 + 2

2 + 1

0 + 3

 

이고.

 

dp[3][1]  에 j 를 1 늘이는 경우

뒤에 0 을 붙여준다.

 

3 + 0  (다른 순서도 인정하므로 이 경우도 +1 이 된다.)

 

따라서 dp[3][2] = 4 가 된다.

 

같은 논리로 뒤 점화식도 동일하게 계산된다.

 

 

2차원 배열일 시에 i, j 의 각 경우의 수를 dp로 나눠준다는 것을 명심해야겠다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

#define MOD 1000000000

int main() {
    int N, K;
    cin >> N >> K;

    // dp[i][j]: 숫자 i를 j개의 숫자의 합으로 표현하는 경우의 수
    vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));

    // 초기화
    for (int j = 1; j <= K; j++) {
        dp[0][j] = 1; // 숫자 0을 j개의 숫자의 합으로 표현하는 방법은 1가지
    }

    // 점화식 계산
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }

    // 결과 출력
    cout << dp[N][K] << endl;
    return 0;
}