챕터3-21. DP | 문제 풀이4 - (4) 백준 No.2225 : 합분해

합분해 문제

* 어려워서 깊은 이해는 못하겠지만 암기는 할 수 있을 듯 하다.
- https://www.acmicpc.net/problem/2225

문제요약

N과 K값이 주어지면 0~N의 수 K개로 N을 나타낼 수 있는 모든 경우의 수를 구하고

그 수를 1,000,000,000로 나눈 나머지를 출력하라.

해결 방법

1. D 정의
D[K][N] = "K개의 수를 더해서 합이 N이 되는 경우의 수"

마지막 항이 L값을 가진다면 이전 항들의 합은 N-L임
그리고 L을 분리시킨다면 K-1개의 수를 더해서 합이 N-L이 되는 경우의 수가 됨.
따라서, D[K][N]은 다음의 점화식으로 구할 수 있음

 

이렇게 맨 뒤의 항을 하나씩 분리시키는 과정이 반복될 때
'K'와 'N'을 입력받으면
K는 1~'K' 의 범위를 가지고              -> 최대 K
N는 0~'N'의 범위를 가지고             -> 최대 N
L은 0~N의 범위를 가짐                   -> 최대 N

 

이것을 그대로 for문으로 나타내면 3중 for문이 되어 아래와 같고, 시간복잡도는 O(K * N * N)가 된다.

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

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 
= O(KN^2)

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

long long d[201][201];

int main()
{
    int n, k;
    cin >> n >> k;

    d[0][0] = 1;

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

    cout << d[k][n] << "\n";
}

추가. <깊은 이해를 통해 메모리를 절감하는 방법>
위의 코드상에서 d[i][j] += d[i-1][j-l]; 부분을 살펴보면 d[i]를 구하기 위해 d[i-1] 즉, 바로 전의 것만 참조하여 구하고 있다.
따라서 왼쪽 인덱스가 1일 땐 오른쪽 인덱스를 0으로, 왼쪽 인덱스가 0일 땐 오른쪽 인덱스를 1로 해주면 두 메모리를 서로 번갈아가며 사용하게 된다.
왼쪽을 d[i%2], 오른쪽을 d[1-(i%2)] 이 되게 해주면 사용되는 메모리를 획기적으로 줄일 수 있다.

시도해보았는데 정답이 맞지 않아서 일단 이건 보류....

d[i%2][j] += d[1-(i%2)][j-l];
d[i%2][j] %= 1000000000;

강의에서 1차원 배열로 문제를 풀 수 있는 방법을 보여주기도 하였는데, 위에 있는 것 까지만 해도 이해하기 벅차기 때문에
이만하고 넘어가자. 차후 이해가 깊어지면 통찰할 수 있길 바라면서..