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

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

영상강의: https://fastcampus.co.kr/courses/210773/clips/

영상보다 쉬운 해설: https://guy-who-writes-sourcecode.tistory.com/43

"dp를 어떻게 정의하는가가 상당히 어렵고 이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다."  ==>>그동안 내가 공부했던 점화식을 구하는데 사용했던 최적의 원리를 적용하기 너무 어렵다(최적해의 부분해가 또다시 그것의 부분문제의 최적해가 된다는 것을 적용하기 힘듬).

dp문제의 특징은 이미 이전의 값은 구해졌다고 가정하고 시작한다. 그 구해진 값을 통해서 이번값을 어떻게 구하는지만 해결하면 된다(점화식). 지금값과 이전값의 다른점은 오직 인덱스가 하나줄었냐, 하나 커졌냐에 불과하기 때문이다.


파일합치기: 코테에서는 이 정도면 가장 어려운 유형임. 안나올 가능성이 크지만 이 문제의 기본 아이디어를 다른 문제에 적용하여 해결할 수 있음. 
"dp를 어떻게 정의하는가가 상당히 어렵고 이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다."

dp[i][j]=i에서 j까지 합하는데 필요한 최소비용. (이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다)
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+sum(A[i]~~A[j]))

기존의 배열은 변경되지 않으므로 sum(A[i]~~A[j])은 고정값임. 따라서 우리가 구해야 하는 것은 최소가 되는 dp[i][k]+dp[k+1][j]임. 

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까지 부분합) 이 될 것이다.

즉 dp[i][j]는 dp[i][divide]+dp[divide+1][j]+sum[j]-sum[i-1] 의 값중에서 가장 작은 값이 된다는 것!!!

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

 

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]
     */

}