[java 백준] 골드 3 /11066번 파일합치기

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

11066번: 파일 합치기

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static int n;
 
    public static long [][]dp;
 
    public static int p;
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        p=Integer.parseInt(br.readLine());
 
 
        for(int i=0;i<p;i++){
            int k=Integer.parseInt(br.readLine());
            dp=new long[k+1][k+1];
 
            long[] sum=new long[k+1];
 
 
            StringTokenizer st=new StringTokenizer(br.readLine());
 
 
 
            //j까지 순서대로 파일을 합친값
            sum[0]=0;
 
            for(int j=1;j<=k;j++){
                dp[j][j]=Integer.parseInt(st.nextToken());
                sum[j]=sum[j-1]+dp[j][j];
 
            }
 
            //인접한 두 파일
 
            for(int j=1;j<=k-1;j++){
                dp[j][j+1]=dp[j][j]+dp[j+1][j+1];
            }
 
 
 
            
            //dp[1][k]의 최소를 알고 싶은거
 
            for(int j=2;j<=k;j++){//끝점
                for(int s=j-1;s>0;s--){ //시작점
 
                    dp[s][j]=Integer.MAX_VALUE;
                    for(int l=s;l<=j-1;l++){//중간 지점
 
 
                        dp[s][j]=Math.min(dp[s][j],dp[s][l]+dp[l+1][j]);
 
 
                    }
                    //어떤게 밑에서 올라왔는지 모르겠으면 올라가기 전에 j에서 s까지 더해주면 됨
                    //이번 회차에 j부터 s까지더한 값을 누적. 다음번에 쓰려고
                    dp[s][j]+=sum[j]-sum[s-1];
 
                }
 
            }
 
 
 
 
            System.out.println(dp[1][k]-sum[k]);
 
 
 
 
 
        }
 
 
 
 
 
 
    }
 
}

 

dp[i][j] 가 무엇인지 생각해보면 i부터 j까지 파일을 합친 누적합이다. 

두개씩 파일을 합친다음에 최종적으로 하나의 파일로 합치기 위해 i부터 j까지 합친걸 더해준다. 

 

dp[2][3]을 보자. 얘는 dp[2][2]+dp[3][3]을 이루어져 있다. 그러면 2부터 3까지 파일을 합치는 경우의 수는 30+30이다. 이전에 파일 합친 것은 없기에 60이 그대로 나온다. 

 

dp[1][3]을 살펴보자. 이것은 dp[1][1]+dp[2][3]이 가장 작은 경우이다. 40+60=100을 하고 이전에  파일 합친것을 누적해야하므로  2부터 3까지 파일을 합쳤던 60을 더해서 

100+60=160이 된다.

 

하지만 이전에 누적된것을 현재 단계에서 찾아서 더해주기란 매우 어렵다. 그래서 차라리 이전에  i부터 j까지 파일 합친걸 누적 하고 올라오는게 어떨까? 라는 생각을 해볼 수 있다. 그래서 앞에서 최종적으로 하나의 파일로 합치기 위해 i부터 j까지 합친걸 더해줘야 한다고 한것이다.

 

그러면 dp[2][3]은 dp[2][2]+dp[3][3]+sum[3]-sum[0]

 

dp[1][3]은 dp[1][1]+dp[2][3]+sum[3]-sum[0]을 해주면 된다.

 

여기서 sum[n]은 1부터 n까지 순서대로 더한 값이다.