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

---

0. 문제

 

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

 

1. 아이디어

 

예를 들어 (3, 3) 즉 0부터 3까지의 정수 중에서 3개를 더해 3을 만드는 경우의 수는 아래와 같다.

 

1. 숫자 0을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 3로 하는 경우의 수

2. 숫자 1을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 2로 하는 경우의 수

3. 숫자 2을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 1로 하는 경우의 수

4. 숫자 3을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 0로 하는 경우의 수

 

top-down 방식으로 이렇게 쭉쭉 내려가다보면 어느 순간 ( ??, 1 ) 이라는 경우를 만난다.

 

이때 ( ??, 1 )은 1가지 숫자를 더해서 ??을 만들어야 하니 반드시 1이 된다.

(또한 같은 논리로 ( ??, 0 )은 반드시 0이 됨을 알 수 있으니 두 경우를 미리 초기화해준다)

 

따라서 ( ??, 1 )을 만났을 때 1을 return 해주므로 재귀를 이용해 답을 구할 수 있다.

 

2. 소스코드

 

#include <iostream>
#define DIV 1000000000
long long dp[201][201];
int dmp(int n, int k)
{
    if (k == 0) return 0;
    if (k == 1) return 1;
 
    if (dp[n][k] != 0) return dp[n][k];
 
    int result = 0;
    for (int i = 0; i <= n; i++)
    {
        result += dmp(i, k - 1);
        result %= DIV;
    }
    dp[n][k] = result;
 
    return dp[n][k];
}
int main()
{
    int N, K;
    std::cin >> N >> K;
 
    std::cout << dmp(N, K);
}

 

3. 결과

 

 

4. 피드백

 

• 재귀 함수를 이용해서 잘 풀어냈다!!

• 문제는 오버플로우 문제를 해결하는데 시간을 많이 썼다. 몽땅 DIV로 나눠서 저장을 하다보니까 정작 필요한 계산에는 엉뚱한 값이 들어가게 되어서 찾느라고 헤맸다. 변수에 값이 어떻게 들어가는지를 잘 쫓아가자!

---