[BOJ 11066번] 파일 합치기(JAVA)

www.acmicpc.net/problem/11066

11066번: 파일 합치기

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   
   public static void main(String args[]) throws Exception {
	   int T=Integer.parseInt(br.readLine());
	   for(int iter=0;iter<T;iter++) {
		   int N=Integer.parseInt(br.readLine());
		   String str[]=br.readLine().split(" ");
		   int arr[]=new int[N];
		   for(int i=0;i<N;i++) {
			   arr[i]=Integer.parseInt(str[i]);
		   }
		   bw.write(function(arr)+"\n");
	   }
	   bw.flush();
	   bw.close();
	   
   }
   
   public static int sum(int[] arr, int s, int e) {
	   if(s==0) return arr[e];
	   else return arr[e]-arr[s-1];
   }
   
   public static int function(int[] arr) {
	   int dp[][]=new int[arr.length][arr.length];
	   int s[]=new int[arr.length];
	   s[0]=arr[0];
	   for(int i=1;i<arr.length;i++) {
		   s[i]=s[i-1]+arr[i];
	   }
	   for(int i=0;i<arr.length-1;i++) {
		   dp[i][i+1]=arr[i]+arr[i+1];
	   }
	   for(int gap=2;gap<arr.length;gap++) {
		   for(int i=0;i+gap<arr.length;i++) {
			   int j=i+gap;
			   dp[i][j]=Integer.MAX_VALUE;
			   
			   for(int k=i;k<j;k++) {
				   dp[i][j]=Math.min(dp[i][k]+dp[k+1][j]+sum(s, i, j), dp[i][j]);
			   }
		   }
	   }
	   return dp[0][arr.length-1];
   }
}

문제가 어려워서 아래 블로그 링크를 참고해서 풀었습니다.

m.blog.naver.com/tjdwns0920/221135677693

[DP] 동적계획법 - 파일 합치기

dp[i][j]는 i번째부터 j번째 인덱스까지의 최소 합을 의미합니다.

dp[i][j]=dp[i][k]+dp[k+1][j]

위 문장이 핵심인데요, dp[i][j]는 i번째부터 k번째 인덱스까지의 최소합 + k+1번째부터 j번째 인덱스까지의 최소합 입니다.

삼중 포문을 이용해 이 문장을 돌려서 정답을 구할 수 있었습니다.