[BaekJoon] 11066 파일 합치기 (Java)

1.  문제 링크

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

2.  문제

요약

• 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 합니다.
• 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 하나의 파일을 만듭니다.
• 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로 하나의 파일로 합칩니다.
• 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정하고 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합치는 데에 필요한 최소비용을 계산하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 두 번째 줄부터 각 테스트 케이스가 주어집니다. 각 테스트 케이스의 첫 번째 줄에 3보다 크거나 같고 500보다 작거나 같은 양의 정수인 소설을 구성하는 장의 수를 나타내는 K가 주어지고 두 번째 줄에 10,000보다 작거나 같은 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수들이 K개 주어집니다.
• 출력: 모든 장을 합치는데 필요한 최소비용을 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int K;
	static int[] sizes, sum;
	static void input() {
		Reader scanner = new Reader();
		int test_num = scanner.nextInt();
		for(int test = 1; test <= test_num; test++) {
			K = scanner.nextInt();
			sizes = new int[K + 1];
			sum = new int[K + 1];
			for(int chapter = 1; chapter <= K; chapter++) {
				sizes[chapter] = scanner.nextInt();
				sum[chapter] = sum[chapter - 1] + sizes[chapter];
			}
			solution();
		}
	}
	
	static void solution() {
		int[][] dp = new int[K + 1][K + 1];
		for(int chapter = 1; chapter <= K; chapter++) {
			for(int index = 1; index + chapter <= K; index++) {
				int to = index + chapter;
				dp[index][to] = Integer.MAX_VALUE;
				for(int divide = index; divide < to; divide++) {
					dp[index][to] = Math.min(dp[index][to], dp[index][divide] + dp[divide + 1][to] + sum[to] - sum[index - 1]);
				}
			}
		}
		sb.append(dp[1][K]).append('\n');
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}