BOJ) 파일 합치기 (11066 번)

파일 합치기

11066번: 파일 합치기

DP로 분류된 문제인데, 정답률에 비해 굉장히 어렵게 느껴졌다.

연속된 소설 파일들을 합치는데,  연속이 되도록 파일을 합쳐야한다.

즉, 인접한 두 파일만을 합칠 수 있을 때, 가장 최소 비용을 구하는 문제다.

 

이 문제는 풀지 못했다.

정말 모르겠어서 다른 분들의 풀이를 참고해서 블로그를 포스팅한다.

참고한 링크는 하단에 걸어두었다.

 

dp[i][j]는 i부터 j까지 합쳐지는데 최솟값을 저장한다. ( i ~ j 장 까지 합치는데 드는 최소 비용)

이를 점화식으로 세우면, 아래와 같은 식이 나온다.

 

dp[i][j] = dp[i][mid] + dp[mid+1][j] + (i~j까지의 부분합)

 

i와 j, mid를 대입해서 보면, 

dp[1][2] = min(dp[1][2], dp[1][1]+dp[2][2] + sum[2]-sum[0])
dp[1][3] = min(dp[1][3], dp[1][1]+dp[2][3] + sum[3]-sum[0]) 
             or  min(dp[1][3], dp[1][2]+dp[3][3] + sum[3]-sum[0])

이와 같은 식이 나온다.

 

 

위의 부분합을 사용해주기 위해 입력 받을 때, 파일을 그대로 받는 것이 아니라 누적합(sum)으로 저장을 해주어 사용한다.

 

 1번째 for문 : gap

 2번째 for문 : start 

 3번째 for문 : mid -> start <=mid < end

 

gap => i

start => j

end => i+j

mid => j ~ i+j -1 ( j + k )

 

 

코드

 

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

public class CombineFile_11066 {
    final static String NEW_LINE = "\n";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<testCases; i++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] sum = new int[n];
            sum[0] = Integer.parseInt(st.nextToken());
            for(int j=1; j<n; j++) {
                sum[j] = Integer.parseInt(st.nextToken()) + sum[j-1];
            }
            sb.append(solution(n, sum)).append(NEW_LINE);
        }
        br.close();
        System.out.println(sb.toString());
    }

    private static int solution(int n, int[] sum) {
        int[][] dp = new int[n][n];

        for(int i=1; i<n; i++) {
            for(int j=0; j<n-i; j++) {
                dp[j][j+i] = Integer.MAX_VALUE;
                for(int k=0; k<i; k++) {
                    int cost = dp[j][j+k] + dp[j+k+1][j+i] + sum[i+j];
                    if(j-1 >=0) {
                        cost -= sum[j-1];
                    }
                    dp[j][j+i] = Math.min(dp[j][j+i], cost);
                }
            }
        }
        return dp[0][n-1];
    }
}

 

REFERENCE

js1jj2sk3.tistory.com/3

melonicedlatte.com/algorithm/2018/03/22/051337.html

kunkunwoo.tistory.com/101