백준 11066번 파일 합치기 G3 - DP 누적합

정리 잘해보자고

 

 

처음엔 이게 뭐지 감을 못잡았다. 무슨말이래

예제만 해도 값이 다달라~

 

파일은 바로 옆에있는것만 합칠 수 있고, 순서에 따라 합이 달라지는데 우리는 최소값을 구해주면 된다.

누적합 문제죠~?~

범위를 2차원 배열로 정해서 DP로 범위를 나눠주기로 했다. 위 예제만 봐도 알겠지만 연산이 가장 적은게 훌륭하다.

 

최종 값은 결국 두 덩이를 합치는것이다. 하나를 A 하나를 B로 정한다면

합쳐진 A와 합쳐진 B가 더해져서 값을 구하는것 이므로 범위를 정하고, Mid를 조정해서 최소값을 찾아주면 되겠다.

 

범위를 늘려나가면서 저장해 준다.

range 변수를 1부터 증가시켜 N 까지 더한 값으로 올라가고, start와 end 변수로 인덱스를 할당한다.

범위의 최소값을 구하고, 누적합을 통해 중간 연산을 더해준다. -> 누적합은 end에서 start-1을 빼주면 되겠다.

예제는 1부터 4까지 합이므로 dp[1][4] 까지 구해 dp[1][4]를 출력해주면 되겠다.

mid 변수를 통해 중간에서 움직이며 값을 정리한다.

 

👀 점화식은

dp[start][end] = Math.min(dp[start ][ end ] , dp[start][mid] + dp[mid + 1][end] + 누적합( sum[end] - sum[start-1] ));

dp[1][4] = dp[1][2] + dp[3][4] + sum[4] - sum[0]; 예제의 인풋이라면 이 경우가 최소값에 들어가게 되겠다.

 

 

import java.util.*;
import java.io.*;
 
public class Main {// Boj_11066_파일 합치기
    static StringBuilder sb;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[][] dp = new int[N + 1][N + 1];
            int[] sum = new int[N + 1];
 
            st = new StringTokenizer(br.readLine());
 
            for (int i = 1; i <= N; i++) {
                int value = Integer.parseInt(st.nextToken());
                sum[i] = sum[i - 1] + value;
            }
            // 1부터 K의 부분합을 구해야한다.
            // 1,2+3 과 1, 2+3 중 최소값을 DP에 저장한다.
            // 수가 많아진다면?
            // 최종적으로 묶어지는 두개의 합을 구하는 과정이므로 한 묶음을 A와 B라면
            // mid로 범위를 나누어 누적합을 더해주면 된다.
            // 1부터 N 범위의 값을 다 더해준 값과 비교해야한다.
            for (int range = 1; range < N; range++) {
                for (int start = 1; start + range <= N; start++) {
                    int end = start + range;
                    dp[start][end] = Integer.MAX_VALUE;
 
                    for (int mid = start; mid < end; mid++) {
                        // dp[1][3] = Math.min(dp[1][2] + dp[3][3], dp[1][1] + dp[2][3])
                        dp[start][end] = Math.min(dp[start][end],
                                dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1]);
                    }
                }
            }
            System.out.println(dp[1][N]);
        }
    }
}