b11066. 파일 합치기

 

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

 

 

 

이 문제는 파일을 합치는 문제로써 주어진 파일들을 순서대로 합치면서

최소 비용을 계산하는 것이다.

 

처음에는 이 문제를 보고 그리디 알고리즘으로 풀어야겠다는 생각이 들었다.

그래서 최소힙(Min-Heap)을 사용해 가장 작은 두 파일을 계속 합치는 방식으로 접근했다.

그러나 결과적으로 이 방식은 문제를 제대로 해결하지 못했다.

파일의 순서를 고려하지 않았기 때문이다.

Heap을 활용한 방식은 각 단계에서 비용을 최소화하려고 하지만,

이는 부분적으로만 최적화될 뿐,

전체 비용이 최소가 되는 것을 보장하지 않는다.

또한, 문제의 조건에서 "파일은 주어진 순서대로 합쳐야 한다"는 점을 간과했다.

이 제약을 무시하면 잘못된 결과를 도출할 수밖에 없다.

직접 예제 데이터를 입력해 본 결과,

틀린 답이 나왔고, 이에 대한 원인을 분석하면서 접근 방식을 다시 생각하게 되었다.

 

문제를 다시 들여다보니,

파일의 순서를 유지하며 최소 비용을 계산하려면

**동적 계획법(DP)**을 사용하는 것이 적합했다.

DP는 특정 구간의 최적 값을 계산하고 이를 점진적으로 확장해

전체 문제를 해결하는 방식이다.

 

이 문제에서는 DP와 함께 누적 합(prefix sum)을 활용해

구간 합을 빠르게 계산하도록 설계할 수 있었다.

해결 과정에서 가장 중요한 점은 dp[i][j]를 정의하는 것이었다.

여기서 dp[i][j]는 i번 파일부터 j번 파일까지를 합치는 데 필요한 최소 비용을 의미한다.

이 값을 구하기 위해 구간을 나누는 기준점 k를 설정하고,

dp[i][j]를 이전 결과들을 기반으로 계산했다.

구간의 총 크기는 누적 합을 사용해 효율적으로 계산했으며,

이렇게 채워진 DP 테이블의 최종 값인 dp[0][N-1]이 우리가 찾는 최소 비용이다.

잘못된 풀이와 올바른 풀이를 비교하며,

문제의 조건을 정확히 이해하는 것이 얼마나 중요한지 다시 한 번 깨달았다.

처음에는 직관적으로 접근해도 맞는 풀이처럼 보였지만,

조건을 무시한 접근은 결국 실패로 이어졌다.

이를 통해 문제를 푸는 데 있어 제약 조건을 면밀히 분석하고,

그에 맞는 알고리즘을 선택하는 것이 얼마나 중요한지 배울 수 있었다.

 

 

import java.io.*;
import java.util.Arrays;
public class Main {

    static int T, N;
    static int[][] dp;
    static int[] prefixSum,fileSize;

    private static void init(BufferedReader br) throws IOException {
        N = Integer.parseInt(br.readLine());
        fileSize = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        dp = new int[N][N];
        prefixSum = new int[N];

        prefixSum[0] = fileSize[0];
        for (int i = 1; i < N; i++)
            prefixSum[i] = prefixSum[i-1] + fileSize[i];
    }

    private static void logic() {
        for (int d = 1 ; d < N; d++){
            for (int i = 0; i < N - d; i++) {
                int j = i + d;
                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i ; k < j ; k++){
                    int cost = dp[i][k]+dp[k+1][j]+(prefixSum[j] - (i > 0 ? prefixSum[i-1]:0));
                    dp[i][j] = Math.min(dp[i][j],cost);
                }
            }
        }
        System.out.println(dp[0][N-1]);
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T ; t++){
            init(br);
            logic();
        }
    }
}

// Heap을 이용하여 순서를 고려하지않은 잘못된 풀이

//public class Main {
//
//    static int T, N, answer;
//
//    static PriorityQueue<Integer> pq;
//
//    private static void logic(){
//        while(pq.size()>=2){
//            int sum = pq.poll()+pq.poll();
//            answer += sum;
//            pq.add(sum);
//        }
//    }
//
//    private static void init(BufferedReader br) throws IOException {
//
//        pq = new PriorityQueue<>();
//        answer = 0;
//        N = Integer.parseInt(br.readLine());
//        StringTokenizer st = new StringTokenizer(br.readLine());
//
//        while(st.hasMoreTokens())
//            pq.add(Integer.parseInt(st.nextToken()));
//
//    }
//
//    public static void main(String[] args) throws IOException {
//
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        T = Integer.parseInt(br.readLine());
//        for (int t = 0; t < T ; t++){
//            init(br);
//            logic();
//            System.out.println(answer);
//        }
//    }
//
//
//}