[백준 11066 : JAVA] 파일 합치기 / DP + 최적화

문제

---

 

 

 

풀이

---

DP[i][j]를 i에서 j까지의 최소비용이라고 하면, 해당 문제의 점화식은 다음과 같다.

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k + 1][j])  (단, i < k < j)

 

위의 점화식은 총 3개의 변수가 각각의 for문을 구성해 O($N^{3}$)의 시간 복잡도가 걸린다.

for (int i = 2; i <= K; i++) {
    for (int j = i - 1; j > 0; j--) {
        dp[j][i] = Integer.MAX_VALUE;
        for (int k = j; k <= i; k++) {
            dp[j][i] = Math.min(dp[j][i], dp[j][k] + dp[k + 1][i]);
        }
        dp[j][i] += (sum[i] - sum[j - 1]);
    }
}

 

위의 코드로도 문제는 풀리지만, 더 나아가서 Knuth Optimization이라고 하는 DP 최적화 기법 중 하나를 적용해보자.

(커누스 최적화는 아직 잘 모르겠네요... 자세히 알고 싶으신 분들은 아래 참고자료에 적어둔 링크로 들어가보세요 !)

 

Knuth Optimization는 점화식이 다음의 세 가지 조건을 만족할 때 사용할 수 있다.

1. DP 점화식의 형태
   D[i][j] = $min_{i<k<j}$(D[i][k] + D[k][j]) + C[i][j]
   
   
2. Quadrangle Inequality (사각부등식)
   C[a][c] + C[b][d] $\le$ C[a][d] + C[b][c] $\quad (단, a \le b \le c \le d)$
   
   
3. Monotonicity (단조성) 
   C[b][c] $\le$ C[a][d] $\quad (단, a \le b \le c \le d)$

 

 

A[i][j]를 위 조건 1번에 나온 점화식에서 D[i][j]가 최소가 되도록 하는 k 값이라고 하면 다음의 식이 성립한다.

A[i][j - 1] $\le$ A[i][j] $\le$ A[i + 1][j]

 

위 부등식을 통해 O($N^{3}$) ---> O($N^{2}$) 의 시간 복잡도로 해결할 수 있게 된다.

for (int d = 2; d <= K; d++) {
    for (int i = 0; i + d <= K; i++) {
        int j = i + d;
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = E[i][j - 1]; k <= E[i + 1][j]; k++) {
            int val = dp[i][k] + dp[k][j] + (sum[j] - sum[i]);
            
            if (dp[i][j] > val) {
                dp[i][j] = val;
                E[i][j] = k;
            }
        }
    }
}

 

 

 

코드

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int K = sc.nextInt();
            int[] arr = new int[K + 1];
            int[] sum = new int[K + 1];
            int[][] dp = new int[502][502];
            int[][] kk = new int[502][502]; // Knuth 최적화를 쓰기 위해 점화식 형태를 맞춰주기 위함.

            for (int i = 1; i <= K; i++) {
                arr[i] = sc.nextInt();
                sum[i] = sum[i - 1] + arr[i];
            }

            for (int i = 1; i <= K; i++) {
                dp[i - 1][i] = 0;
                kk[i - 1][i] = i;
            }

            // DP 최적화 기법 중 하나인 Knuth Optimization을 사용한 코드 O(N^2)
            for (int d = 2; d <= K; d++) {
                for (int i = 0; i + d <= K; i++) {
                    int j = i + d;
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = kk[i][j - 1]; k <= kk[i + 1][j]; k++) {
                        int v = dp[i][k] + dp[k][j] + (sum[j] - sum[i]);
                        if (dp[i][j] > v) {
                            dp[i][j] = v;
                            kk[i][j] = k;
                        }
                    }
                }
            }
            sb.append(dp[0][K]).append("\n");

            // DP 최적화없이 그냥 DP로 푼 코드. O(N^3)
            // j에서 i까지의 최소 비용. (j < k < i)
//            for (int i = 2; i <= K; i++) {
//                for (int j = i - 1; j > 0; j--) {
//                    dp[j][i] = Integer.MAX_VALUE;
//                    for (int k = j; k <= i; k++) {
//                        dp[j][i] = Math.min(dp[j][i], dp[j][k] + dp[k + 1][i]);
//                    }
//                    dp[j][i] += sum[i] - sum[j - 1]; // 마지막에 전체 합을 한 번 더해준다.
//                }
//            }
//            sb.append(dp[1][K]).append("\n");

        }

        System.out.println(sb.toString());
    }
}

 

 

 

참고자료

---

[1] codeforces.com/blog/entry/8219

[2] blog.myungwoo.kr/98

[3] m.blog.naver.com/PostView.nhn