백준 11066번 : 파일 합치기 [Java]

www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

DP 문제는 쉬워도 점화식 세우는 부분에서 항상 어려움을 겪는다.

알고나면 별거 아닌데, 막상 접하면 어렵다.

이 블로그까지 찾아왔다는 이야기는 이 전에 이미 풀이를 작성한 블로그에서 보여주는 풀이가 이해하는 부분에 있어서 헤매다 왔을것이라 생각한다. 한번 잘 설명해보겠다.

 

파일 합치기는 메모이제이션 문제임으로 점화식을 세울 필요성이 있다.

 

따라서 먼저 식에 대한 정의가 필요하다.

 

dp[ i ][ j ] 를 무엇이라 정의할 것인가?

dp[ i ][ j ]는 i번 페이지부터 j번 페이지까지 페이지를 합한 최솟값이라 정의하겠다.

 

점화식?

우선적으로 dp[ i ][ i ] 일때 생각해보자. i페이지부터 i페이지까지의 합은 즉 i번째 페이지의 값인 novel[ i ] 가 될 것이다.

 

그럼 dp[ i ][ i + 1] 은?

dp[ i ][ i + 1 ]은 novel[ i ] + novel[ i + 1 ] 이 될것이다.

 

 

그럼 dp[ i ][ i + 2]는 어떻게 될 것이냐? 

dp[i][i] + dp[i+1][i+2] + (novel[i]  + novel[i + 1] + novel[i + 2]) , dp[i][i+1] + dp[i + 2][i + 2] + (novel[i] + novel[i + 1] + novel[i + 2]) 값중에 작은 값이 되지 않겠는가?

 

이를 다시 점화식으로 풀어보자.

 

dp[i][j] = divide가 i + 1 부터 시작해서 j - 1까지 순회하면서 비교했을때 dp[i][i + divide] + dp[divide + 1][j] + sum(i부터 j까지 부분합) 이 될 것이다.

 

그리고 페이지를 묶어내야 함으로 두장씩 묶고, 세장씩 묶는 과정들이 필요하다.

 

for 1장부터 n장까지 묶기 n <= k(몇장을 묶을것인가?
	for 1부터 k까지 from + n <= k  (어디부터 묶기 시작할것인가)
    		for 1부터 k까지 divide < from + n (범위가 주어졌을때 특정 지점으로 나눠서 최대값 구하기)

 

그럼 위와 같은 3차원 반복문이 나올것이다. 이를 코드화하면 

 

for (int n = 1; n <= k; n++) {
    for (int from = 1; from + n <= k; from++) {
        int to = from + n;
        dp[from][to] = Integer.MAX_VALUE;
        for (int divide = from; divide < to; divide++) {
            dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
        }
    }
}

 

위와 같이 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    public static void main(String[] args) throws Exception {
        int t;

        t = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < t; tc++) {
            int k;
            int[] novel;
            int[] sum;
            int[][] dp;

            k = Integer.parseInt(br.readLine());
            novel = new int[k + 1];
            dp = new int[k + 1][k + 1];
            sum = new int[k + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                novel[i] = Integer.parseInt(st.nextToken());
                sum[i] = sum[i - 1] + novel[i];
            }

            for (int n = 1; n <= k; n++) {
                for (int from = 1; from + n <= k; from++) {
                    int to = from + n;
                    dp[from][to] = Integer.MAX_VALUE;
                    for (int divide = from; divide < to; divide++) {
                        dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
                    }
                }
            }

            System.out.println(dp[1][k]);
        }

    }
    /**
     * memoization dp
     * 점화식
     * dp[i][j] = i부터 j장까지 합치는 비용
     * dp[i][i] = novel[i]
     * dp[i][i + 1] = novel[i] + novel[i+1]
     */

}