백준 11066. 파일 합치기

 

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

11066번: 파일 합치기

 

 

 

1. 문제 설명

 

소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 

이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.

 

두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

 

2. 접근법

 

"이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다." 부분을 통해 해당 문제는 그 하위 문제로 분할이 가능함을 알 수 있다

(이때, 연속이 되도록 파일을 합쳐나감이 중요함)

 

소설 완성본은 두 개의 파일이 합쳐져서 만들어진 것이고

그 두 개의 파일도 더 작은 파일들로 합쳐져서 만들어진 것이다

여기서 합쳐지는 과정에서 비용이 발생하고 소설 완성본을 만들 때 최소 비용을 구해야한다

 

즉, 소설 완성본을 구성하는 두 개의 파일을 분할하고 각각의 파일들 또한 두 개의 파일들로 분할하는 과정을 반복해서

최소 비용을 구해나감

 

일반화를 시켜보면 파일이 i부터 j까지 합쳐진 큰 파일이 있다고 가정했을 때

해당 파일은 k를 기준으로 i~k까지의 합쳐진 파일과 k+1~j까지 합쳐진 파일을 합친 결과라고 할 수 있다

이때, k에 따라서 i부터 j까지 합쳐진 큰 파일을 만드는 비용이 달라지므로 k는 변수로 다뤄서 i부터 j까지 합쳐진 파일을 만드는 최소 비용을 구해야한다

 

 

 

 

3. 설계

 

1. dp를 재귀적으로 호출하자(top-down)

- 파일의 합쳐진 범위를 i, j라고 가정

- i == j 일 때 0 반환 -> 하나의 파일

- dp 메모이제이션을 통해 중복 회피

-재귀 호출(dp 적용)

 

 

4. 코드

import java.util.*;
import java.io.*;



public class Main {

    static int[] a;
    static int[][] dp;

    static int go(int i, int j) {
        if (i == j) {
            return 0;
        }

        if (dp[i][j] != -1) {
            return dp[i][j];
        }

        int ans = -1;
        int sum = 0;
        for (int k=i; k<=j; k++) {
            sum += a[k];
        }

        for (int k=i; k<j; k++) {
            int tmp = go(i, k) + go(k+1, j) + sum;
            if (ans == -1 || ans > tmp) ans = tmp;
        }

        dp[i][j] = ans;
        return ans;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());

        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] numberStr = br.readLine().split(" ");

            a = new int[n+1];
            dp = new int[n+1][n+1];

            for (int i=1; i<=n; i++) {
                a[i] = Integer.parseInt(numberStr[i-1]);
                Arrays.fill(dp[i], -1);
            }

            int ans = go(1, n);
            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
    }
}