BOJ G3 11066 파일 합치기 JAVA

11066번: 파일 합치기

---

문제 읽기

일단 상당히 오래 걸렸다. DP 문제라고 하는데 DP 문제인지 전혀 몰랐다.

 

일단 처음에는 문제를 잘못 이해해서 마구잡이로 작은 것들끼리 합쳤다. 그랬더니 예제부터 틀려서 문제를 다시 읽어보고 깨달았다.

 

문제를 봤을 때는 약간 트리?모양이 생각났다. leaf 노드부터 하나씩 합쳐지는.. 그래서 내가 모르는 알고리즘인가 하고 분류를 봤는데.. 이게 머냐 DP였다. (자괴감 ㅠㅠ)

근데 DP인걸 알아도 모르겠어서 결국엔 풀이를 찾아봤다. 아래 글을 참고해서 이해하기 쉽게 정리해봤다.

[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)11066번, 파일 합치기

---

문제 풀기

왜 DP인가

문제에서 주어진 경우를 생각해보자.

A1, A2, A3, A4 총 네 개의 여러 파일이 있다고 가정했을 때, 파일은 다음과 같이 합쳐질 수 있다.

 

이것만 보면 잘 와 닿지 않지만, 다음과 같이 구간을 나눠볼 수 있다.

 

크게 하나의 파일이 되기 위해서는, 두 개의 구간이 합쳐진 형태이고, 또 그 안을 보면 또 두 개의 구간이 합쳐진 형태가 나온다.

 

즉, 만약 완전 탐색을 통해 이 문제를 해결한다면 저런 작은 구간들이 중복된 연산이 되기 때문에 불필요한 연산을 매우 많이 수행하게 된다. 이를 개선하여 DP를 활용할 수 있는 것이다.

 

DP로 어떻게 나타낼 것인가. 점화식을 세워보자.

그렇다면 이 문제를 어떻게 DP로 나타낼 것인지가 두 번째 문제이다.

 

아래 그림을 다시 보면 특정 구간에 대해서 값이 반복적으로 사용되고 있다. 따라서 이차원 DP를 통해 특정 구간에 대한 값을 저장할 수 있다.

 

즉, DP 배열에는 다음과 같이 저장된다.

DP[i][j] : 파일 i부터 파일 j까지 합쳤을 때 비용의 최솟값

 

예시를 들어보자.

 

A1 한 개의 파일이 있다면 파일을 하나로 합치는 데에는 얼만큼의 비용이 들까?

파일 하나이다. 즉, 합칠 필요가 없고 비용도 들지 않는다.

따라서 0 만큼의 비용이 든다.

즉, DP[i][i] = 0이다.

 

그럼 A1, A2 두 개의 파일이 있다면 두 파일을 하나로 합치는 데에는 얼만큼의 비용이 들까?

파일 두 개이기 때문에 각 파일의 크기를 더한 만큼이 비용이 된다.

즉 cost[1] + cost[2] 만큼의 비용이 든다.

즉, DP[i][i+1] = cost[1] + cost[2]이다.

 

그럼 A1, A2, A3 세 개의 파일이 있다면 세 파일을 하나로 합치는 데에는 얼만큼의 비용이 들까?

파일이 세 개이기 때문에 다음과 같이 두 가지 경우의 수가 나오고, 이 둘 중 최솟값을 저장해야 한다.

 

여기서 파란색으로 표시한 부분은 각각의 파일을 임시 파일로 더하는 부분이고, 빨간색으로 표시한 부분은 파란색으로 합쳐진 임시파일(또는 파일)들을 합쳐서 하나의 파일로 만드는 부분이다.

즉, DP[i][j]라는 값을 구하는 모든 경우에 DP의 이전 값도 활용하지만, cost[i] + cost[i+1] +… cost[j]라는 모든 파일들의 비용의 합을 더해주어야 한다. 따라서 이런 부분을 고려해서 처음에 cost 값을 입력 받을 때, 부분합 형태로 입력 받으면 계산하는 비용을 절약할 수 있다.

 

즉, 다음과 같은 형태로 입력 받는다.

costSum[i] : 1~i까지의 비용의 합

 

그러면 식이 이렇게 바뀌게 되고, 이 둘 중 최솟값을 저장함으로써 DP[1][3]을 구할 수 있다.

 

그렇다면 파일이 4개 이상일 때는 어떻게 될까? 위와 마찬가지로 파일들을 두 구간으로 나누는 모든 경우를 생각하며, 각각 두 구간의 합에 대해 최솟값을 구할 것이다.

 

DP[1][4]를 구하는 경우를 간단하게 수식으로만 써보면,

• DP[1][1] + DP[2][4] + costSum[4] - costSum[0]
• DP[1][2] + DP[3][4] + costSum[4] - costSum[0]
• DP[1][3] + DP[4][4] + costSum[4] - costSum[0]

이렇게 세 가지 경우가 나오고, 이 중에서 최솟값을 저장할 수 있다. 즉 일반화하여 표현하면 다음과 같다.

DP[i][j] = Math.min(DP[i][s] + DP[s][j] + costSum[4] - costSum[0])

 

여기서 costSum[4] - costSum[0]의 경우에는 모든 경우에 다 동일하게 더해지는 상수값이므로, 결국 다음과 같이 바꿀 수 있다.

DP[i][j] = Math.min(DP[i][s] + DP[s][j]) + costSum[4] - costSum[0]

 

그러면 최종적으로 다음과 같은 형태로 점화식을 세울 수 있다.

i : 첫 번째 구간의 시작

j : 두 번째 구간의 끝

s : 구간이 나뉘는 부분(==첫 번째 구간의 끝이자, 두 번째 구간의 시작 직전)

 

코드 짜기 - DP 배열을 채우는 순서

그렇다면 위의 점화식에 따라서 DP 배열을 어떻게 채워나가고, 결과값을 구할 수 있을까?

예제 1의 테케 1번을 예시로 DP 배열을 그려보면 다음과 같다.

우리가 최종적으로 원하는 값은 DP[1][N]이다. 따라서 DP[1][N]을 구하기 위해서는 어떤 값들이 필요한지 체크했고, 그 결과 위 표에서 볼 수 있는 형광펜으로 칠한 부분이 필요했다.

 

즉, 노란색 화살표 순서대로 DP 배열을 채우면 된다.

 

코드 짜기

그렇다면 실제 코드를 어떻게 짜야 할까?

 

이렇게 표를 그대로 DP[i][j]로 표현해보았고, 그 결과 다음과 같이 3중 for문을 활용하여 코드를 작성할 수 있다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_11066_파일합치기 {
    static int[] costSum;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while(T-- > 0){
            int N = Integer.parseInt(in.readLine()); //3~
            costSum = new int[N+1];
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i = 1; i < N+1; i++){
                costSum[i] = Integer.parseInt(st.nextToken()) + costSum[i-1];
            }

            int[][] dp = new int[N+1][N+1];
            //출발지 i, 목적지 j, 중간에 나눠지는 부분 mid
            for (int j = 2; j <= N; j++){
                for (int i = j-1; i >= 1; i--){
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int s = i; s < j; s++){
                        dp[i][j] = Math.min(dp[i][j], dp[i][s] + dp[s+1][j]);
                    }
                    dp[i][j] += (costSum[j] - costSum[i-1]);
                }
            }
            sb.append(dp[1][N]).append("\\n");
        }
        System.out.println(sb);
    }
}