[Algorithm] Baekjoon 2225번 : 합분해

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

2225번: 합분해

int dp[201][201] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, k;
    
    cin >> n >> k;
    
    for (int i = 0; i <= n; ++i)
    {
        dp[1][i] = 1;
    }
 
    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            for (int l = 0; l <= j; ++l)
            {
                dp[i][j] = (dp[i][j] + dp[i - 1][l]) % 1000000000;
            }
        }
    }
 
    cout << dp[k][n];
}

 

동전문제랑 비슷한가.. 싶다가도 사용할 수 있는 갯수제한 때문에 다르게 생각해야하는 문제.

뿐만아니라 더할 때 1+2와 2+1을 다른 갯수로 취급해야한다. 

 

여기서 DP[K][N]은 K개만큼의 숫자를 활용해서 N을 만드는 경우의 수라 가정한다.

 

DP[4][6]을 생각해보자.

 

4개를 활용해서 6을 만들어야 한다.

만약 마지막에 0을 더했다면? 3개를 활용해서 6을 만드는 경우의 수가 나온다.

마지막에 1을 더했다면? 3개를 활용해서 5를 만드는 경우의 수가 나온다.

마지막에 2를 더했다면? 3개를 활용해서 4를 만드는 경우의 수가 나온다.

마지막에 3를 더했다면? 3개를 활용해서 3를 만드는 경우의 수가 나온다.

마지막에 4를 더했다면? 3개를 활용해서 2를 만드는 경우의 수가 나온다.

마지막에 5를 더했다면? 3개를 활용해서 1를 만드는 경우의 수가 나온다.

마지막에 6를 더했다면? 3개를 활용해서 0를 만드는 경우의 수가 나온다. 

.

.

.

 이 모든 경우의 수를 합치면 DP[4][6]이 나온다.

즉,

DP[K][N]을 구하기위해서는 DP[K-1][0]부터 DP[K-1][N]까지 더해주면 된다.

 

갯수제한에다가 순서가 다르면 다른경우의 수로 취급하는것때문에 사실 어떻게 접근해야할지 잘 몰랐는데, 이 문제덕분에 이런 접근방법도 있다는 걸 알았다.