[백준 11066] 파일 합치기 / 자바 /dp

#문제         

레벨: G5
알고리즘: dp 
풀이시간: 1
힌트 참조 유무:

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

---

#문제 풀이        

그리드 문제로도  착각할 수 있지만 연속된  파일들만 합칠 수 있기 때문에 그리드 문제는 아니다. (그리드 문제라면 파일을 합치고 정렬하고 합치고를 반복하기 때문에 연속된 파일임을 보장하지 않음)

 

dp[i][j] =  i ~ j까지 파일 합쳤을 때 최솟값

+행은 시작인덱스를 나타내고 열은 끝인덱스를 나타낸다.

{2,3}이면 2에서부터 3까지 더했을 때 최솟값이다.

 

dp 배열을 이 방향으로 채워진다. 빨간색 숫자는 채워지는 순서를 뜻한다. 아래 코드르 보면 알겠지만 이중 for문이 뜻하는 것은 파란색 방향을 말하는 것이다.

가장 깊숙히 있는 for문은 그 인덱스에서 가장 작은 값을 배정하기 위해 반복문을 도는 것이다. 6번쨰인 (1,4)인덱스 값을 구할 때를 예시를 들어보겠다. 처음 보라색 동그라미끼리 더해 Math.min하고  다음 반복문은 초록색 세모끼리 더해 Math.min하고 다음 반복문은 파란색 네모끼리 더해 Math.min하는 거다.

 

---

#풀이 코드      

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 테스트 케이스 수

        for (int t = 0; t < T; t++) {
            int K = scanner.nextInt(); // 장의 수
            int[] files = new int[K];
            int[] sum = new int[K + 1];

            // 파일 크기 입력 및 누적 합 계산
            for (int i = 0; i < K; i++) {
                files[i] = scanner.nextInt();
                sum[i + 1] = sum[i] + files[i];
            }

            // DP 테이블 초기화
            int[][] dp = new int[K][K];

            // 길이에 따라 최소 비용 계산
            for (int len = 1; len < K; len++) {
                for (int i = 0; i + len < K; i++) {
                    int j = i + len;
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], 
                                            dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i]);
                    }
                }
            }

            // 결과 출력
            System.out.println(dp[0][K - 1]);
        }
        scanner.close();
    }
}