11066번 - 파일 합치기

2024-09-03

#JAVA#백준

문제 링크

문제 풀이 시간 : 2시간

문제 요약:

•
여러 개의 파일을 합쳐 하나의 파일을 만들려고 한다.

•
파일을 합치는 최소 비용을 구하라.

문제 풀이

이 문제를 보자마자 우리가 알고리즘 시간에 배웠던 허프만 트리가 생각났다.

그래서 바로 우선순위 큐로 코드를 쉽게 짤 수 있었다.

코드

Java

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

public class Main {
    public static PriorityQueue<Integer> pq;

    public static int calc() {
        int temp = 0;
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            temp += a + b;
            pq.add(a + b);
        }
        return temp;

    }

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

        for (int i = 0; i < T; i++) {
            pq = new PriorityQueue<>();
            int K = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < K; j++) {
                pq.add(Integer.parseInt(st.nextToken()));
            }
            System.out.println(calc());
        }

    }
}

그런데 예제 부터가 틀리게 나온다…

2번 예제에서 답은 864라고 나오지만

내가 작성한 코드에서는 826이 나온다.

그래서 내가 코드를 잘못 짰나? 하고 직접 허프만 트리를 그려보았다.

근데 그래도 826이 나온다..

이건 내가 더 낮은 수가 나오는데 답이 틀릴수가 없다 생각하고

문제의 오류를 찾았구나???

했는데??

알고보니

임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고

라는 문장이 문제 속에 숨어있었다.

즉, 파일의 순서대로 합쳐야 되는 것이다.

내가 짠 우선순위 큐를 활용한 풀이는 순서를 섞어버리기 때문에 해당 문제의 조건을 만족하지 못한 것이다.

그래서 다시 풀이를 생각하다가 이건 DP다!! 라는 생각을 했다.

Java

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());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N + 1][N + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[j][j] = Integer.parseInt(st.nextToken());
            }


            for (int j = 0; j < N - 1; j++) {
                for (int k = 1; k <= N - 1 - j; k++) {
                    int temp = Math.min(arr[k][k + j] + arr[k + 1 + j][k + 1 + j], arr[k][k] + arr[k + 1][k + 1 + j]);
                    arr[k][k + 1 + j] = temp;
                }
            }
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    System.out.printf(arr[j][k]+" ");
                }
                System.out.println();
            }
        }

    }
}

이렇게 어찌저찌 DP 코드를 짜서 파일을 합치긴 하는데…

최소 비용을 구하는 방법을 도저히 모르겠어서

결국 형님들의 코드를 참고하게 되었다.

여기서 arr은 dp를 계산한 배열이고,

arr[i][i]는 i번째 페이지 부터 i번째 페이지 까지의 합이다.

즉, arr[i][i] = num[i]

arr[i][i+1] = num[i] + num[i+1]이 된다.

그럼 arr[i][i+2]는?

arr[i][i] + arr[i+1][i+2] + (num[i] + num[i+1] + num[i+2])

arr[i][i+1] + arr[i+2][i+2] + (num[i] + num[i+1] + num[i+2])

중 작은 값이 될 것이다.

그래서 결국 arr[i][j]를 구하려면?

i ≤ temp < j 인 temp를 가지고

arr[i][temp]+arr[temp+1][j]+num[i] + num[i+1] + … +num[j]

를 다 해보면 되는 것이다.

결국 아래와 같은 코드가 나오게 된다.

Java

for (int j = 1; j <= N; j++) {
                for (int from = 1; from + j <= N; from++) {
                    int to = from + j;
                    arr[from][to] = Integer.MAX_VALUE;
                    for (int t = from; t < to; t++) {
                        arr[from][to] = Math.min(arr[from][to], arr[from][t] + arr[t+1][to] + sum[to] - sum[from - 1]);
                    }
                }
            }

최종 코드

Java

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());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N + 1][N + 1];
            int[] num = new int[N + 1];
            int[] sum = new int[N + 1];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int j = 1; j <= N; j++) {
                num[j] = Integer.parseInt(st.nextToken());
                sum[j] = sum[j - 1] + num[j];
            }

            for (int j = 1; j <= N; j++) {
                for (int from = 1; from + j <= N; from++) {
                    int to = from + j;
                    arr[from][to] = Integer.MAX_VALUE;
                    for (int t = from; t < to; t++) {
                        arr[from][to] = Math.min(arr[from][to], arr[from][t] + arr[t+1][to] + sum[to] - sum[from - 1]);
                    }
                }
            }

            System.out.println(arr[1][N]);
        }

    }
}