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

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

0부터 N까지 K개의 정수를 더해 합이 N이 되는 경우의 수를 구하여라. 더하는 순서가 바뀐 경우, 다른 경우로 센다.

---

시간복잡도 어림하기

브루트 포스 알고리즘

 간단하게 경우의 수를 어림해봅시다.

n = 20, k = 4일때,
(20, 4)의 경우의 수는 (20, 3) + (19, 3) + (18, 3) + ... (1, 3) + (0, 3) 입니다.
또, (20, 3)의 경우의 수는 (20, 2) + (19, 2) + (18, 3) + ... (1, 2) + (0, 2) 이고
(19, 3)의 경우의 수는 (19, 2) + (18, 2) + (17, 2) + ... (1, 2) + (0, 2) 입니다.

이후 생략

 이를 트리의 형태로 나타난다면 자식 노드 수가 현재 노드의 n값 + 1인 트리 형태가 될 것입니다. 트리의 자식인 2인 이진트리라고 생각해도 트리의 높이인 k의 최댓값이 200이므로 노드의 수가 2^200인데, 트리의 자식의 수는 대부분이 2보다 크므로 제한 시간 내에 모든 노드를 계산하기 어렵습니다.

 따라서 브루트 포스를 통해 이 문제를 해결하기 어렵습니다.

 

DP 알고리즘

 n과 k의 최댓값이 200이므로 모든 n, k에 대한 값을 배열에 저장할 수 있습니다. 또한, 위에서 경우의 수를 계산할 때 반복되는 순서쌍들이 있는데 이들을 한 번씩만 계산하도록 구현한다면 경우의 수를 확실히 줄일 수 있습니다. 모든 순서쌍들이 한 번만 계산되므로 총 계산 횟수는 200 x 200 = 40000으로 제한 시간 내에 문제를 해결하기 충분합니다. 따라서 dp 알고리즘을 적용하여 문제를 해결해봅시다.

---

알고리즘 설계하기

 알고리즘은 브루트 포스 알고리즘의 시간복잡도를 계산할 때 사용한 로직을 그대로 사용하겠습니다.

 

 위의 순서쌍들이 생기는 규칙을 보면, 현재 수에서 0부터 현재수까지 빼고, 더할 숫자의 개수도 1 줄이면서 순서쌍을 구하는 것을 볼 수 있습니다. 따라서 다음과 같이 구현합니다.

    for(int i = 0; i <= 현재수; i++){
        ret += solve(현재수 - i, 현재길이 - 1);
    }

  

 이때 더할 숫자의 개수가 1일 때에는 경우의 수가 항상 1이므로 재귀 함수의 기저 조건으로 해당 조건을 추가합니다.

 

 여기까지 구현한 것이 브루트 포스 알고리즘입니다. 하지만 문제를 해결하기 위해서는 한 순서쌍은 한 번만 계산해야합니다. 따라서 메모이제이션을 사용합니다.

 

 가장 먼저 현재수와 현재 길이에 대해 dp배열을 탐색하고 아직 계산되지 않은 순서쌍이라면 위 로직을 실행하여 dp배열을 갱신하고, 이미 계산된 값이 존재한다면 그 값을 그대로 반환하면 됩니다. 코드로는 다음과 같은 형태가 될 것입니다.

int solve(int num, int len){
    /*기저 조건*/
    if(len == 1) return 1;
    
    int &ret = dp[num][len]
    if(ret에 계산된 값이 있다면) return ret;
    
    /*
    	재귀 호출 로직
    */
}

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#define DIV 1000000000
using namespace std;

int n, k, dp[204][204];
int solve(int num, int len){
    /*기저 조건*/
    if(len == 1) return 1;
    
    /*메모이제이션*/
    int &ret = dp[num][len];
    if(ret > 0) return ret;

    ret = 0;
    /*재귀 호출 로직*/
    for(int i = 0; i <= num; i++){
        ret += solve(num - i, len - 1);
        ret %= DIV; //나머지 계산
    }
    return ret;
}
int main(){
    cin >> n >> k;
    cout << solve(n, k);
    return 0;
}

 이 문제에서 결과는 경우의 수를 1,000,000,000으로 나눈 나머지를 구해야하는데 나머지산의 위치를 확인해주시길 바랍니다. 나머지 연산의 위치는 반드시 기존 경우의 수에 추가 경우의 수를 더한 후 나머지 연산을 진행해야합니다.

---