[백준 11066] 파일 합치기

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

11066번: 파일 합치기

 

보자마자 생각난 건 분할 정복이었다..!!!!

예전에 어떤 문제에서 풀은 방식이었던 것 같은데(무슨 문제였는지 기억은 안남..)

i장부터 j장까지의 파일을 합쳤을 때의 최소를 구하여

1장부터 K장까지의 최소를 구하는 방식으로 풀이했다. (값들은 재귀 방식으로 구해짐)

 

(챕터 수의 최대가 500이었고 이는 널널하게 계산 가능할거란 생각이 들어 전수 조사를 하게 되었다.)

 

주의할 점

범위의 최소값을 저장하는 과정에서

저장될 수 있는 최대값 MAXFILE이 500(챕터 수)*10000(파일의크기) 일거라고 생각하였다.

하지만 파일을 합하는 비용은 중첩되어 계산되므로 이 기준값은 잘못된 것이다..

따라서 널널하게 1000000000으로 재설정해주었다..

 

 

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

public class Main {
    static int[][] min;
    static final int MAXFILE = 1000000000; 
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        int T = Integer.valueOf(line);
        for (int cnt = 0; cnt < T; cnt++) {
            //chapter 수
            int K = Integer.valueOf(br.readLine());
            line = br.readLine();
            min = new int[K + 1][K + 1];    //해당 범위에서의 최소값 저장
            int[] size = Arrays.stream(line.split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            for (int i = 0; i < size.length; i++) {
                min[i + 1][i + 1] = size[i];
            }
            mergeFiles(1, K);
            bw.write(String.valueOf(min[1][K]) + "\n");

        }

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

    private static void mergeFiles(int beginF, int endF) {

        int comp=0;
        int minSum = MAXFILE;
        for (int mid = beginF; mid < endF; mid++) {
            min[beginF][endF] += min[mid][mid];
            if (min[beginF][mid] == 0)
                mergeFiles(beginF, mid);
            if (min[mid + 1][endF] == 0)
                mergeFiles(mid + 1, endF);

            if (mid == beginF && mid == endF - 1) {
                comp = 0;
            }else if(mid==beginF || mid==endF-1){
                if(mid == beginF){
                    comp = min[mid + 1][endF];
                } else if (mid == endF - 1) {
                    comp = min[beginF][mid];
                }
            } else {
                comp = min[beginF][mid] + min[mid + 1][endF];
            }
            minSum = (minSum > comp) ? (comp) : minSum;

        }
        min[beginF][endF] += (min[endF][endF] + minSum);
    }
}