[Gold-3] 11066번 | 동적계획법(DP) | 자바(Java)

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

 

해당 문제는 백준 "동적계획법2" 단계의 문제이다.

DP 알고리즘 이해를 위해 간략한 설명과 함께 문제를 풀이해보겠다.

 

1. 동적 계획법(Dynamic Programming, DP)

: 큰 문제를 작은 하위 문제로 나누어 각 문제의 결과를 저장하고, 재사용해 효율적으로 해결하는 알고리즘 기법이다.

DP를 사용하면 중복 계산을 피할 수 있어 반복적인 구조가 있는 문제를 더 빠르게 풀 수 있다.

 

문제의 핵심

파일을 합치려면 인접한 두 파일을 하나로 합쳐야 하고, 이때 두 파일 크기의 합이 비용이 된다.

이렇게 파일을 하나로 합칠 때 최소 비용을 구하려면 파일을 합치는 순서를 잘 정해야 할 것이다.

예를 들어, 작은 파일들끼리 먼저 합치는 것이 비용을 줄이는 데 유리할 것이다.**

 

 

동적 계획법 접근 방식

(1) 하위 문제로 나누기 :

- "i번째 파일부터 j번째 파일까지 하나로 합치기 위한 최소 비용"

- dp[i][j]를 사용하여 i에서 j까지의 파일을 하나로 합치기 위한 최소 비용을 저장

(2) 부분 문제 최적화 :

- 큰 문제 dp[0][K-1]를 해결하기 위해 더 작은 문제들 (dp[i][j]에서 i<j)를 차례로 계산해가며 누적 비용을 저장

(3) 저장 및 재사용 :

- 각 구간의 최소비용을 미리 구해놓고 재사용함으로써, 같은 구간에 대한 중복 계산을 피한다.

 

 

우선 코드를 보면서 한줄 한줄 설명하자면,

여기서 K는 파일의 개수이다. 해당 문제에서

4

40 30 30 50

을 입력으로 받았으므로 여기서 K는 4가 됨을 알 수 있다. 

출력 : 70(40+30) + 80(30+50) + 150(70+80) = 300

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++) {
            int cost = dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i];
            dp[i][j] = Math.min(dp[i][j], cost);
        }
    }
}

 

 

dp[i][j]에 저장되는 값은 i에서 j까지의 파일을 하나로 합치기 위한 최소 비용.

이때, 우리가 구하는 구간 i~j 사이에서 어디서 분할(k 위치)하느냐에 따라 비용이 달라진다.

 

• len : len은 부분 문제의 길이를 나타내며, 1부터 K-1까지 순차적으로 증가한다.
  len=1이면 인접한 두 파일을 합치는 최소 비용을 계산하는 것이고, len=K-1이면 전체 파일을 하나로 합치는 것
• for(int i=0;i+len < K;i++) : i는 구간의 시작 위치이고, i+len < K 조건으로 끝 위치가 배열 범위를 넘지 않도록 한다.
• j=i+len : j는 구간의 끝 위치이다. 예를 들어 len=1일 때 i=0이면 j=1이 되어, 인접한 파일 두 개(0번과 1번)를 합치는 최소 비용을 계산하는 것이다.
• dp[i][j] = Integer.MAX_VALUE : 최소 비용을 찾기 위해 초기값을 큰 값으로 초기화
• for(int k=i;k<j;k++) : 구간 i부터 j까지를 합치기 위해 k를 기준으로 구간을 나눈다. dp[i][k]와 dp[k+1][j]는 각각 i~k와 k+1~j까지의 최소 비용을 의미한다. 이 둘을 합치고, 구간 전체를 합치는 비용을 더하여 최소 비용을 계산한다.

그럼 최종적으로 dp[i][j] 배열을 채우면서 dp[0][K-1]에 최종 결과가 저장된다.

dp[0][K-1]은 전체 파일을 하나로 합치는 최소 비용을 나타낸다.

 

---

 

이해가 안될 수 있으니 예시를 살펴보자.

 

우리는 파일을 처음부터 끝까지 한 번에 합치는 대신,

먼저 i부터 j까지 중간 구간을 k에서 나누어 두 개의 구간으로 나눈 후 각 구간의 비용을 계산한다.

 

파일 [40, 30, 30, 50]을 구간을 나누어 합치는 방법을 생각해보면

 

k=1일 때:

* dp[i][k]는 40과 30을 합친 최소 비용

* dp[k+1][j]는 30과 50을 합친 최소 비용

* 여기에 두 구간을 합치는 비용까지 고려하여 최소 비용을 찾음

 

이런 방식으로 k가 i부터 j-1까지의 모든 가능한 분할 지점을 시도하여 그 중 최소 비용을 dp[i][j]에 저장험

 

sum[j+1] - sum[i] : 현재 구간 전체를 한 번에 합치는 데 필요한 비용을 의미

이 값은 두 부분으로 나눈 구간들을 다시 하나로 합칠 때의 비용이다.

• 예를 들어 i=0, j=3이라면 sum[4] - sum[0]은 [40, 30, 30, 50] 전체의 합이 됨. 이는 이 구간을 합칠 때 추가로 드는 비용

따라서 dp[i][j]는 최소 비용으로 두 구간을 합친 결과에 현재 구간의 크기를 더해 업데이트된다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());  // 테스트 케이스 수

        for (int t = 0; t < T; t++) {
            int K = Integer.parseInt(br.readLine());  // 파일의 개수
            int[] files = new int[K];
            int[] sum = new int[K + 1];
            int[][] dp = new int[K][K];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < K; i++) {
                files[i] = Integer.parseInt(st.nextToken());
                sum[i + 1] = sum[i] + files[i];  // 부분합 계산
            }

            // 동적 계획법 테이블 채우기
            for (int len = 1; len < K; len++) {  // 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++) {
                        int cost = dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i];
                        dp[i][j] = Math.min(dp[i][j], cost);
                    }
                }
            }

            sb.append(dp[0][K - 1]).append("\n");
        }
        System.out.print(sb);
    }
}