[오답노트] BOJ 11066: 파일 합치기 - JAVA

---

출처 : https://www.acmicpc.net/problem/11066
난이도 : 골드 3
풀이날짜 : 2022-12-26

---

---

풀이

아이디어

c1, c2, c3, c4에서 합치는 방법에 대해서 다음과 같이 생각할 수 있다.

(((c1 + c2) + c3 ) + c4)
(c1 + (c2 + c3)) + c4
...
이런 식으로 묶을 수 있는데 이런 식으로 연속적으로 묶이게 됩니다.

이를 점화식으로 하면
다음과 같다.

dp[i][j]를 i부터 j까지의 연속된 것 중 가장 작은 것
dp[i][j]에 값은 i와 j 사이의 값 k를 뽑고 dp[i][k] + dp[k+1][k] + sum[i][j]들을 비교하며 가장 작은 값을 고르게 됩니다.

---

코드

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

public class No11066 {
	
	static int K;
	static int[] arr;
	static int[][] dp, sum;
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int ti=0; ti<T; ti++) {
			input();
			pro();
		}
		br.close();
	}

	private static void input() throws IOException {
		K = Integer.parseInt(br.readLine());
		arr = new int[K];
		sum = new int[K][K];
		dp = new int[K][K];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<K; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
	}

	private static void pro() {
		for(int i=0; i<K; i++) {
			for(int j=i; j<K; j++) {
				sum[i][j] = arr[j];
				if(j-1>=0)
					sum[i][j] += sum[i][j-1];
			}
		}
		
		for(int len = 1; len<K; len++) {
			for(int i=0; i+len < K; i++) {
				int j = i + len;
				dp[i][j] = Integer.MAX_VALUE;
				
				for(int k=i; k<j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j]);
				}
			}
		}
		System.out.println(dp[0][K-1]);
	}
}

---

결과

---

느낀점

이해를 하는데 많은 시간이 걸렸고 다시 풀어보는데 많이 막혔습니다. 이 문제는 다시 리뷰할 것!