[알고리즘 / 백준] 11066 - 파일 합치기

www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

이 문제의 경우, 앞뒤로 붙어있는 두 파일을 합치는 방식으로 모든 경우를 확인하여 문제를 해결할 수 있습니다.

 

예제를 살펴보면 파일은 [40, 30, 30, 50] 이렇게 비용이 들고 앞에서부터 [a, b, c, d] 파일이라고 할 때,

a 부터 d 파일까지 모두 합치는 경우는 

(1) b+c+d 를 먼저 합치고 a+b+c+d 가 되는 비용 ((b+c+d) + (a+b+c+d))

(2) a+b 를 먼저 합치고 c+d 를 합치고 a+b+c+d 가 되는 비용 ((a+b) + (c+d) + (a+b+c+d))

(3) a+b+c 를 먼저 합치고 a+b+c+d 가 되는 비용 ((a+b+c) + (a+b+c+d))

이렇게 총 3가지 경우가 됩니다.

 

(파일을 어떻게 합치든 a 부터 d 까지 파일을 합치는 경우 모두 a+b+c+d 의 경우를 포함해야 하므로 이는 sum 배열로 미리 저장을 해둡니다.)

 

따라서 이차원 배열 dp[i][j] 를 생성하고 이 배열에는 i 부터 j 까지 파일을 합치는데 드는 최소 비용을 저장합니다.

 

i 부터 j 까지 파일을 합치는데 드는 비용은 다음과 같이 구할 수 있습니다.

먼저, dp 배열에 dp[i][i + 1] 에 files[i] + files[i + 1] 즉, 현재 위치(i+1)에 바로 이전 파일과 현재 파일의 비용 합을 저장합니다.

이제 a+b+c 의 경우 나올 수 있는 비용을 살펴보면

(1) ((b+c) + (a+b+c))

(2) ((a+b) + (a+b+c))

이 두가지 경우 중 최소값을 저장하면 됩니다.

 

다음으로 a+b+c+d 의 경우 나올 수 있는 경우를 살펴보면 

(1) ((b+c+d) + (a+b+c+d))

(2) ((a+b) + (c+d) + (a+b+c+d))

(3) ((a+b+c) + (a+b+c+d))

이렇게 3가지 경우가 있으므로 이 중 최소값을 저장하면 됩니다.

 

 

이를 점화식으로 표현하면, dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sumDist(sum, i, j) 로 나타낼 수 있는데

이때 sumDist 는 i 부터 j 까지의 파일을 더한 총합을 구하는 것입니다.

 

파이썬 코드는 다음과 같습니다. Pypy3 로 제출해야 시간 초과를 피할 수 있습니다.

from sys import stdin

t = int(stdin.readline())
for _ in range(t):
    k = int(stdin.readline())  # 총 파일 수
    files = list(map(int, stdin.readline().split()))  # 리스트로 파일 합칠 때 비용 저장
    sums = [files[0]]
    for i in range(1, len(files)):
        sums.append(sums[i - 1] + files[i])  # 순차적으로 이전까지의 합 + 현재 파일 합칠 때 비용을 저장

    dp = [[0] * k for _ in range(k)]
    for i in range(len(files) - 1):
        dp[i][i + 1] = files[i] + files[i + 1]  # 현재 파일과 다음 파일을 더한 값을 저장

	# 위 그림과 같이 순차적으로 i 부터 j 까지의 파일을 합칠 때 최소 비용을 dp 에 저장
    for j in range(2, len(files)):  # 열
        i = 0
        while i + j < len(files):  # 행
            for k in range(i, i + j):
                sum_dist = sums[i + j] - sums[i - 1] if i != 0 else sums[i + j]
                if dp[i][i + j] == 0:
                    dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + sum_dist
                else:
                    dp[i][i + j] = min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + sum_dist)
            i += 1

    print(dp[0][-1])  # 이중 배열에서 첫번째 배열의 마지막 저장 값을 출력

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
            int[] files = new int[k];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < files.length; j++) {
                files[j] = Integer.parseInt(st.nextToken());
            }

            int[] sum = new int[k];
            sum[0] = files[0];
            for (int s = 1; s < sum.length; s++) {
                sum[s] = sum[s - 1] + files[s];
            }

            bw.write(String.valueOf(solution(files, sum)));
            bw.newLine();
        }

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

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

        return sum[end] - sum[start - 1];
    }

    private static int solution(int[] files, int[] sum) {
        int[][] dp = new int[files.length][files.length];

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

        for (int j = 2; j < dp.length; j++) {
            for (int i = 0; i + j < dp.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][dp.length - 1];
    }
}