[BOJ 11066] 파일 합치기

(https://www.acmicpc.net/problem/11066)

이 문제는 Dynamic Programming을 이용하는 문제이며, Knuth's Optimization을 이용하여 최적화를 한다.

 

Knuth's Optimization 게시글 (https://wogud6792.tistory.com/20)

 

위 문제는 파일을 합치는 모든 경우 중에서, 합이 최소가 되는 경우를 찾는 문제이다. 

 

만약 C1~C4를 합친다면, C1 + C2~C4 또는, C1~C2 + C3~C4 또는, C1~C3 + C4와 같이 부분문제가 만들어질 수 있다.

이 때, C2 ~ C4, C1 ~ C3의 경우도 또 다시 부분문제로 나뉘어 질 수 있다. 

ex) C2 + C3~C4 또는 C2~C3 + C4    /   C1 + C2~C3 또는 C1~C2 + C3

즉, C1~C4를 합치는 경우의 수는 5가지로 나오게 된다. 

 

문제 해결 아이디어는, 가장 아래단계부터 시작해서 점점 합쳐나가는 방식을 이용한다. 

 

이를 dp의 기존 알고리즘을 이용하면 아래와 같다.

#define MAX 1<<30
#define _CRT_SECURE_NO_WARNINGS
 
#include<stdio.h>
#include<algorithm>
using namespace std;
 
int novel[500];
int p_sum[500];
int dp[500][500];
int main(void) {
    int T, m,  i, j, k; 
    scanf("%d", &T);
    for (m = 0; m < T; m++) {
        int K;
        scanf("%d", &K);
        for (i = 0; i < K; i++) {
            scanf("%d", &novel[i]);
            if (i == 0) p_sum[i] = novel[i];
            else p_sum[i] = p_sum[i - 1] + novel[i];        //첫번째부터 i번째까지 파일크기 합
        }
        for (i = 1; i < K; i++) {                            //구하려는 구간의 길이 = i
            for (j = 0; j+i < K; j++) {                        //구간의 시작 index = j
                dp[j][j+i] = MAX;
                    for (k = j; k < j+i; k++) {            
                        if(j == 0)    dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k + 1][j+i] + p_sum[j+i]);
                        else dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k + 1][j+i] + p_sum[j+i] - p_sum[j-1]);
                    }
            }
        }
        printf("%d\n", dp[0][K - 1]);
    }
}

 

이 코드는 $ O(n^3) $의 시간복잡도를 갖게 된다. 

 

i) p_sum[i]는 첫번째부터 i번째까지의 파일 크기 합을 나타낸다. 

 

ii) 그리고 첫번째 반복문에서 i는 구간의 길이를 의미한다. 1씩 증가시켜가면서 구간을 점점 키워나간다.

 

iii) 두번째 반복문에서 j는 구간의 시작 index를 의미한다.

만약 i = 3인 경우에, 0~2 , 1~3 , 2~4 , .... 와 같은 방식으로 구간을 구해나간다.

 

iv) 세번째 반복문에서 k는 구하려는 구간을 둘로 나누는 역할을 한다. 

만약 i = 5이고 j = 2, k = 4인 경우라면, 2~4와 5~7의 구간으로 나눈 후, 이를 이용하여 2~7의 구간을 구한다. 

 

하지만 $ O(n^3) $의 시간복잡도는 비효율적이므로 knuth's Optimization을 이용하여 최적화를 시킨다. 

 

 

#define MAX 1<<30
#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<algorithm>
using namespace std;
 
int novel[500];
int p_sum[500];
int dp[500][500];
int A[500][500];
int main(void) {
    int T, m,  i, j, k; 
    scanf("%d", &T);
    for (m = 0; m < T; m++) {
        int K;
        scanf("%d", &K);
        for (i = 0; i < K; i++) {
            scanf("%d", &novel[i]);
            if (i == 0) p_sum[i] = novel[i];
            else p_sum[i] = p_sum[i - 1] + novel[i];        //첫번째부터 i번째까지 파일크기 합
        }
        for (i = 0; i < K; i++) {    //cost 배열 초기화
            A[i][i] = i;
        }
        for (i = 1; i < K; i++) {
            for (j = 0; j+i < K; j++) {
                dp[j][j+i] = MAX;
                    for (k = A[j][j+i-1]; k <=A[j+1][j+i]; k++) {
                        int temp;
                        if(j==0) temp = dp[j][k] + dp[k + 1][j + i] + p_sum[j + i];
                        else temp = dp[j][k] + dp[k + 1][j + i] + p_sum[j + i] - p_sum[j - 1];
 
                        if (dp[j][j + i] > temp) {
                            dp[j][j + i] = temp;
                            A[j][j + i] = k;
                        }
                    }
            }
        }
        printf("%d\n", dp[0][K - 1]);
    }
}

위의 방식대로 한다면 세번째 반복문이 수행되는 횟수는 $ O(1) $ 을 만족하게 된다.

따라서 전체 시간복잡도는 $O(n^2)$ 로 나오게 된다.

 

위의 결과(knuth's Optimization)와 아래의 결과(기존 dp)를 비교해보면 시간 차이가 많이 나는 것을 알 수 있다.