[Algorithm] 백준_11066 파일 합치기 java

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합 이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

풀이

검색으로 해결한 문제.
파일이 연속되지 않아도 된다고 생각하고 풀어서 해결이 어려웠다.

1. sum[] 배열에 현재 파일까지의 합을 넣어준다. sum[0]은 file[0]과 같다.

2. dp[K][K] 만큼의 이차원 배열을 선언하고, i부터 j번째 파일을 합치는데 필요한 비용을 넣어준다.

• i == j
  파일이 한 개라는 뜻 이므로 0을 넣어준다.

• dp[i][i+1]
  인접한 두 파일의 합을 넣어주면 된다.
  = file[i] + file[i+1]

• i < k < j
  dp[i][j] = Math.min(dp[i][k] + dp[k+1][j] + sumDist(sum, i, j) )

• sumDist(int[] sum, int start, int end)
  파일의 총 합을 구해놓은 sum배열에서, start와 end 사이의 파일들의 총 합을 구하는 함수이다. 예를 들어 3번~5번 파일의 총 합을 구해야 할 때 사용한다.

소스 코드

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

public class BOJ_11066 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int K = Integer.parseInt(br.readLine());
            String input = br.readLine();
            st = new StringTokenizer(input);

            int[] file = new int[K];
            for (int j = 0; j < K; j++) {
                file[j] = Integer.parseInt(st.nextToken());
            }

            bw.write(String.valueOf(solution(file)));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }

    static int sumDist(int[] sum, int start, int end) {
        if (start == 0) {
            return sum[end];
        } else {
            return sum[end] - sum[start - 1];
        }
    }

    static int solution(int[] file) {
        int[][] dp = new int[file.length][file.length];
        int[] sum = new int[file.length];

        sum[0] = file[0];

        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i-1] + file[i];
        }

        for (int i = 0; i < file.length -1; i++) {
            dp[i][i+1] = file[i] + file[i+1];
        }

        for (int j = 2; j < file.length; j++) { //열
            for (int i = 0; i+j < file.length; i++) { //행
                for (int k = i; k < i + j; k++) {
                    if (dp[i][i + j] == 0) {
                        dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + sumDist(sum, i, i + j);
                    } else {
                        dp[i][i + j] = Math.min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + sumDist(sum, i, i + j));
                    }
                }
            }
        }

        return dp[0][file.length - 1];
    }
}