백준 11066번 : 파일 합치기 | JAVA

 

📌 알고리즘 선택

처음 문제를 읽어봤을 때, 장(chapter)의 크기를 더한 값을 저장해두는 작업이 필수적이겠다는 생각이 들었고, 반복적인 연산을 줄이는 dp가 자연스럽게 떠올랐다. dp를 사용하는 것은 잘 떠오르긴 했지만,, dp의 핵심인 점화식을 어떻게 만들어야할지 고민이 많았다.

 

---

📌 풀이

dp[i][j]를 i번째 장부터 j번째 장까지의 합한 최솟값이라고 하자.

 

그럼 dp[i][i]는 i번째 장 그 자체가 될 것이고,

dp[i][i+1]는 i번째 장(filesize[i])과 i+1번째 장(filesize[i+1])의 합인 filesize[i]+filesize[i+1] 이 될 것이다.

 

dp[i][i+2]는 어떻게 될까?

dp[i][i] + dp[i+1][i+2] + (filesize[i] + filesize[i+1], filesize[i+2])와 dp[i][i+1] + dp[i+1][i+2] + (filesize[i] + filesize[i+1], filesize[i+2]) 중 더 작은 값이 될 것이다.

 

그에 따라,

dp[i][j]는 dp[i][divide] + dp[divide+1][j] + sum(i부터 j까지의 부분합)이 될 것이다.

이때 divide는 i에서 j까지의 수 중 하나이다.

 

---

📌 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        int total = 0; // 결과값

        for(int t = 0; t < T; t++) {

            // 파일 개수
            int K = Integer.parseInt(br.readLine());

            // 파일 담을 배열 및 파일 크기의 합을 담을 배열과 dp 배열
            int[] fileSize = new int[K+1];
            int[] sum = new int[K+1];
            int[][] dp = new int[K+1][K+1];

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int k = 1; k <= K; k++) {
                fileSize[k] = Integer.parseInt(st.nextToken());
                sum[k] = sum[k-1] + fileSize[k];
            }

            // dp 연산 과정
            for(int n = 1; n <= K; n++) { // 몇 개의 장을 묶을 것인가
                for(int from = 1; from + n <= K; from++) { // 어디부터 묶을 것인가
                    int to = from + n;
                    dp[from][to] = Integer.MAX_VALUE;
                    for(int divide = from; divide < to; divide++) {
                        dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide+1][to] + sum[to] - sum[from-1]);
                    }
                }
            }

            // 첫번째 파일부터 K번째 파일까지의 합
            System.out.println(dp[1][K]);

        }

    }

}

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

11066번: 파일 합치기