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

[문제]

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

 

[접근방식]

이 문제는 '다이나믹 프로그래밍' 으로 해결하고자 한다.

 

문제를 읽어보고 든 생각은 백준 11049번 '행렬 곱셈 순서' 문제랑 유사하다. 라는 것이었다.

 

문제 - https://www.acmicpc.net/problem/11049

풀이 - https://notorious.tistory.com/417 

 

'행렬 곱셈 순서' 문제 풀이의 핵심은 "dp[i][j] 를 (i~k) 와 (k+1~j)로 구간을 나눠 해결" 하는 것이다.

 

따라서 이 문제 역시 i번째 파일부터 j번째 파일까지 병합하는 최소 비용을 (i~k) 와 (k+1~j)로 범위를 나눠 해결할 것이다.

 

DP 문제 해결에서 가장 중요한 것은 DP배열의 정의를 확실하게 정립하는 것이다.

DP 배열을 다음과 같이 정의한다.

 

"dp[i][j] = i번째 ~ j번째 까지 파일 병합 최소 비용"

 

DP 점화식은 다음과 같다.

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + 'i~j파일까지 파일크기 누적값'

 

 

[Java 코드]

/**
 * BOJ_11066 파일 합치기
 * https://www.acmicpc.net/problem/11066
 * keyword - 
 */

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine()); //test case
        for (int t = 0; t < T; t++) {

            int K = Integer.parseInt(br.readLine());
            int[] files = new int[K];
            int[] sum = new int[K + 1]; //sum[i] = 0 ~ i-1 까지의 누적합

            //DP정의 : i ~ j 파일 병합 최소비용
            int[][] dp = new int[K][K];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < K; i++) {
                files[i] = Integer.parseInt(st.nextToken());
                sum[i + 1] = sum[i] + files[i];
            }

            //DP 채우기 - (i~k / k+1~j) 로 구간을 나눠 계산
            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++) {
                        // (i~k) + (k+1~j) + (i ~ j 파일크기)
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i]);
                    }
                }
            }


            sb.append(dp[0][K - 1]).append("\n");
        }


        //결과 출력
        System.out.println(sb.toString().trim());
    }
}

 

[Rewind]

1. 어려웠던 점

- '행렬 곱셈 순서' 문제를 통해 접했던 해결방식이었는데도, 조금 바뀐 조건에 막혀 스스로 해결하지 못했다.

- DP 점화식에서 필요한 "i~j 파일 크기 누적합"을 구하는데, 2차원 배열을 이용하여, i~j파일 크기 누적합을 의미하는 sum_files[i][j] 로  구성하여, 불필요하게 복잡한 길로 가게되었다.

- 1차원 배열을 이용하여 sum[j+1] - sum[i] 를 하여 쉽게 구성하는 방식을 생각해내지 못했다.

 

2. 알게된 점

- DP를 활용하여 해결하는 새로운 문제를 접했다.  

 

3. 개선방안

- 지속적인 DP 문제 풀이? 잘 모르겠음.