[백준] 11066 파일합치기

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

11066번: 파일 합치기

---

DP로 해결해야 하는 문제이기 때문에 점화식을 세우는 것이 중요합니다. 점화식은 아래와 같습니다

DP[i][j]: files[i]에서 files[j]까지 합치는 총 비용

 

1 2 3 4 의 파일들이 존재할 때 files[0]에서 files[3]까지 파일을 합치는 방법은 여러가지가 있습니다.

 

(1 + 2) + (3 + 4)

1 + ((2 + 3) + 4)

(1 + (2 + 3)) + 4 

....

 

따라서 시작 지점과 끝 지점의 파일을 모두 더할 때 중간 계산 중 최소 값을 구해야 합니다. 이를 수도 코드로 나타내면 아래와 같습니다.

for j <- start to end-1:
    dp[start][end] = 
         MIN(dp[start][end], dp[start][j] + dp[j+1][end] + (arr[start] + ... + arr[end]))

dp[start][j] + dp[j+1][end]

위 식은 files[start] ~ files[j]까지와 files[j+1] ~ files[end]까지 비용의 합을 의미합니다.

arr[start] + ... + arr[end]

위 식은 file[start] ~ file[end] 까지 합을 의미합니다. 누적 합 알고리즘을 사용하면 쉽게 나타낼 수 있습니다. 

 

예를들어, (1 + 2) + (3 + 4)의 경우 dp[0][1] = 3, dp[2][3] = 7이 됩니다. 그리고 file[0] ~ file[3]의 합은 10입니다.

따라서 위 방식의 최종 비용은 3 + 7 + 10 = 20이 됩니다.

 

이렇게 구한 비용들을 모두 비교하여 최소값을 구하면 문제를 해결할 수 있습니다.

 

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class BOJ11066 {
	private static BufferedReader br;
	public static void main(String[] args) throws NumberFormatException, IOException {
	br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	for (int i=0;i<T;i++) {
	System.out.println(mergeFiles());
	}
	}
	public static int mergeFiles() throws NumberFormatException, IOException {
	int N = Integer.parseInt(br.readLine());
	int[] files = getFiles(N);
	int[] acc = accumulate(files);
	int[][] dp = new int[N][N];
	for (int step=1;step<N;step++) {
	for(int start=0;start<N-step;start++) {
	int end = start + step;
	dp[start][end] = Integer.MAX_VALUE;
	for (int j=start;j<end;j++) {
	dp[start][end] = Math.min(
	dp[start][end],
	dp[start][j] + dp[j+1][end] + acc[end+1] - acc[start]);
	}
	}
	}
	return dp[0][N-1];
	}
	public static int[] accumulate(int[] arr) {
	int[] res = new int[arr.length+1];
	for (int i=0;i<arr.length;i++) {
	res[i+1] = res[i] + arr[i];
	}
	return res;
	}
	public static int[] getFiles(int N) throws IOException {
	int[] files = new int[N];
	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	for (int i=0;i<N;i++) {
	files[i] = Integer.parseInt(st.nextToken());
	}
	return files;
	}
	}

view raw BOJ11066.java hosted with ❤ by GitHub

	from sys import stdin
	from collections import defaultdict
	readline = stdin.readline
	T = int(readline())
	def solve():
	for _ in range(T):
	print(merge_files())
	def merge_files():
	N = int(readline())
	files = list(map(int, readline().split()))
	acc = accumulate(files)
	dp = [[0 for _ in range(N)] for _ in range(N)]
	for step in range(1, N):
	for start in range(N-step):
	end = start + step
	dp[start][end] = float('inf')
	for j in range(start, end):
	dp[start][end] = min(
	dp[start][end],
	dp[start][j] + dp[j+1][end] + acc[end] - acc[start-1])
	return dp[0][N-1]
	def accumulate(arr):
	res = defaultdict(int)
	for i in range(len(arr)):
	res[i] = res[i-1] + arr[i]
	return res
	solve()

view raw BOJ11066.py hosted with ❤ by GitHub