[Kotlin][Algorithm] 11066 - 파일합치기

문제 요약

여러 개의 파일을 하나로 합치는 과정에서 발생하는 비용을 최소화하는 방법을 찾는 문제입니다. 각 파일을 합칠 때, 그 비용은 합치려는 두 파일의 크기 합으로 결정됩니다. 이때, 파일을 합치는 순서에 따라 최종적으로 발생하는 총 비용이 달라질 수 있기 때문에, 최소 비용으로 모든 파일을 하나로 합치는 순서를 찾는 것이 목표이다.

문제 접근

이 문제를 해결하는 가장 직관적인 방법으로는 브루트포스 입니다.
모든 가능한 파일 합치기 순서를 시도하여 최소 비용을 찾는 방법을 사용하면 문제 해결이 가능 합니다.

이렇게 모든 경우의 수를 구한다면
n개 중에 연속된 2개를 선택하는 경우의수 n - 1
이전 결과 n - 1 개 중에 연속된 2개를 선택하는 경우의 수 n -2
...
이전 결과 2 개 중에 연속된 2개를 선택하는 경우 1개

이렇게 (n-1)!의 경우의 수가 나오게 됩니다.
이렇게 여러번의 경우의 수 중 겹치는 중간 부분이 되게 많습니다. 이러한 부분에 대해서 큰 경우의 수에 대해 모두 다시 계산을 진행하면 시간복잡도 초과가 나오게 됩니다.

다이나믹 프로그래밍

하지만 이 문제는 "최적 부분 구조(Optimal Substructure)"와 "중복되는 부분 문제(Overlapping Subproblems)"의 특성을 가지고 있어 다이나믹 프로그래밍을 사용하면 훨씬 효율적으로 해결할 수 있습니다.

[10, 20, 30, 40, 50, 60]인 경우를 생각해 봅시다

[10, 20, 30] 을 합칠 때 최소 값은

첫 번째와 두 번째 파일을 먼저 합치는 경우:
[10,20], [30]

10과 20을 합치는 비용: 30
그 결과(30)를 30과 합치는 비용: 60
총 비용: 30 + 60 = 90

두 번째와 세 번째 파일을 먼저 합치는 경우:
[10], [20,30]

20과 30을 합치는 비용: 50
그 결과(50)를 10과 합치는 비용: 60
총 비용: 50 + 60 = 110

[10, 20, 30]을 합칠 때 최소 비용은 90입니다.

이 최소값은 [10, 20, 30, 40], [10, 20, 30, 40, 50], [10, 20, 30, 40, 50, 60] 등을 여러번 계산할 때 중복되어 사용됩니다.

DP를 사용하면, [10, 20, 30]의 최소 합치는 비용을 한 번만 계산하고, 이후의 계산에서 이 값을 재사용할 수 있습니다. 이는 브루트포스 방식에서 같은 계산을 여러 번 반복하는 것을 방지하여 계산량을 대폭 줄여줍니다.

최적 부분 구조는 전체 문제의 최적 해결책이 그 문제의 부분 문제의 최적 해결책으로부터 구성될 수 있다는 성질을 의미합니다. 이 문제에서는 모든 파일을 합치는 최소 비용을 구하는 문제가 각각의 부분 집합의 파일들을 합치는 최소 비용을 구하는 문제들로 나눌 수 있습니다. 예를 들어, 파일 A, B, C를 합치는 최소 비용을 구하는 문제는 파일 A와 B를 합치는 최소 비용, 파일 B와 C를 합치는 최소 비용, 그리고 그 두 결과를 합치는 비용을 고려하여 해결할 수 있습니다.

중복되는 부분 문제는 다이나믹 프로그래밍의 핵심적인 특성 중 하나로, 문제를 해결하는 과정에서 동일한 작은 문제들이 반복적으로 계산되는 현상을 말합니다. "파일 합치기" 문제에서는 특정한 파일들의 그룹을 합치는 최소 비용이 여러 번 계산될 수 있습니다. 예를 들어, 여러 단계에 걸쳐서 파일 A와 B를 합치는 최소 비용, 파일 C와 D를 합치는 최소 비용 등이 여러 경로를 통해 계산될 수 있습니다.

1. 점화식 설정
   먼저, dp[i][j]를 i번째 파일부터 j번째 파일까지 합치는 데 필요한 최소 비용으로 정의합니다. 우리의 목표는 dp[0][n-1]을 구하는 것이며, 여기서 n은 전체 파일의 수입니다.

2. 부분 문제 해결
   dp[i][j]를 구하기 위해서는, i와 j 사이의 모든 위치 k에 대해 dp[i][k]와 dp[k+1][j]를 합치는 비용을 고려해야 합니다. 이때, 추가로 발생하는 비용은 i부터 j까지의 파일 크기의 합입니다.

코드

fun main() {
    val br = System.`in`.bufferedReader()
    val t = br.readLine().toInt()
    val sb = StringBuilder()
    repeat(t) {
        val n = br.readLine().toInt()
        val files = br.readLine().split(" ").map { it.toInt() }
        sb.append(mergeFiles(n,files)).append("\n")
    }
    println(sb.toString())
}

fun mergeFiles(n : Int, files : List<Int>) : Int {
    val sum = IntArray(n + 1) { 0 }
    val dp = Array(n) { IntArray(n) { 0 } }
    
    // 빠른 부분합을 위한 누적합 배열 
    for (i in 1..n) {
        sum[i] = sum[i - 1] + files[i - 1]
    }

    // d 길이 그룹
    for (d in 1 until n) {
        // i 번째 부터 시작
       for (i in 0 until n - d) {
           // j 까지 
           val j = i + d
           dp[i][j] = Int.MAX_VALUE
           // m은 i와 j사이에 파일을 나누는 위치
           // i에서 j 까지 최소 비용 = [각 m 위치에서 나누었을 때 가장 최소 비용 + i에서 j까지 누적합]
           for (m in i until j) {
               dp[i][j] = dp[i][j].coerceAtMost(dp[i][m] + dp[m + 1][j] + sum[j + 1] - sum[i])
           }
       }
    }

    return dp[0][n - 1]
}

배운점

0~n까지의 여러 경우의 수에 대한 연산이 필요하다면 다이나믹 프로그래밍을 생각해보자
겹치는 부분이 있는지(중복 부분 문제), 각 부분 문제로 나누고 결합했을때 최적의 답이 나오는지(최적 부분 구조)