BOJ_11066 : 파일 합치기

👉 문제링크

---

---

🔸 문제 분석 🔸

• T번의 테스트 케이스로 K개의 양수가 주어진다.
• 연속된 두 값의 합으로 계산했을 때 연산 비용의 최소값을 출력한다.

🔸 문제 풀이 🔸

• K가 500이지만, Brute Force로 확인했을 때 O(K^3) 이상이 나올 것으로 예상해서 더 효율적으로 구하기 위해 DP 를 활용하고자 했다.
• dp 배열은 다음과 같이 구했다.
  • 1번부터 K번 숫자를 합했을 때 최소값을 구하고자 하므로, dp[0][K-1]를 구한다.
    다시 말해 dp 배열은 해당 범위의 최소연산 비용을 저장한다.
  • dp 배열을 채워갈 때, 연속된 두 값을 더해가므로, 중간에 1번 잘라서 좌우 값을 더했을 때의 최소값을 구한다.
  • 따라서 점화식은 다음과 같이 구할 수 있다.
    • K개의 숫자 중 left ~ right 범위를 계산했을 때 최소값 
    • dp[ left ][ right ] = min(dp[ left ][ right ], dp[ left ][ mid ] + dp[ mid + 1][ right ] + (left부터right까지의 합) ]
    • 점화식을 풀이하면, 범위에 해당하는 숫자들의 총합과 좌우측 범위 합을 만들 때 실행 된 비용을 더한 값의 최소값을 찾아야 한다.
    • 따라서 구간합 배열을 만들어 특정 범위의 합을 쉽게 구할 수 있도록 한다.

🔸 코드 🔸

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

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

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

            // Input
            int K = Integer.parseInt(br.readLine());
            int[] files = new int[K]; // 파일 크기
            long[] sumArr = new long[K + 1]; // 누적합

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

            // Dynamic Programming
            // dp[i][j] : i ~ j 범위를 더할 때 계산된 최소값
            // 잘라서 찾기 : 왼쪽 계산값 + 오른쪽 계산값 + files 의 i~j 범위의 합
            long[][] dp = new long[K][K];
            for (int size = 2; size <= K; size++) { // i~j 범위의 크기
                for (int i = 0; i <= K - size; i++) { // 범위 왼쪽 인덱스
                    int j = i + size - 1;           // 범위 오른쪽 인덱스

                    dp[i][j] = Long.MAX_VALUE;

                    for (int l = i; l < j; l++) { // 범위 잘라서 합의 최소값 찾기
                        dp[i][j] = Math.min(dp[i][j], dp[i][l] + dp[l + 1][j] + sumArr[j + 1] - sumArr[i]);
                    }
                }
            }
            sb.append(dp[0][K - 1]).append('\n');
        }
        // Output
        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 특정 구간의 합을 빠르게 구하기 위해 구간합 배열 sumArr를 사용했다.
• sumArr와 dp 배열의 누적값이 아주 커질 수 있으므로, long형을 사용했다.
• 범위를 잘라 사용하기 위해 dp는 2차원 배열로 사용했다.
• dp 배열을 계산할 때, 범위의 크기를 2부터 K까지 키워가며 최소 비용을 계산한다.
• 최종 값인 dp[0][K-1]를 출력한다.

---

🔸 end 🔸

• 직전에 풀었던 BOJ_11049 : 행렬 곱셈 순서와 매우 유사한 문제였다.
  
  • 2차원 dp 배열을 사용하고, 좌우측으로 잘라서 최소값을 구하는 방식이 일치한다.
  • 차이점으로는 구간합 배열이 필요하다는 것이다.
• 직전 문제 풀이가 떠올라서 알고리즘 선택에는 시간이 들지 않았는데, 오히려 직전 풀이와의 차이점을 생각하지 못해서 테스트 케이스 2번을 계속 통과 못했었다.
  • 그래서 1시간 이상 고민하고, 손으로 디버깅도 많이 해봤지만 결국 못찾고 GPT의 점화식 피드백을 받았다.
  • dp배열에 누적할 때, 좌우측 값을 가져오는건 잘 했는데 현재값을 좌우측값의 합이라고 생각해서 x2 를 해버렸다.
  • 결과적으로 누적되야 하는 값은 현재 범위의 들어가는 모든 숫자의 총합이어서 누적합이 필요했다.
  • 고민의 흔적은 다음과 같다....