난이도 : 골드 3
유형 : DP
https://www.acmicpc.net/problem/11066

---

문제 접근

해당 문제는 여러개의 파일을 하나로 합치는 과정에서 필요한 비용의 최솟값을 구하는 문제이다.

2개의 파일을 1개의 파일로 합치는 과정을 최종 1개의 파일이 될 때 까지 반복해야 한다.

예시 1을 보면
[40, 30, 30, 50] 이 주어졌을 때 이 네개의 파일을 하나로 합칠 수 있는 방법은 총 5가지이다.

예시: [40, 30, 30, 50] → 각 파일을 a, b, c, d라고 할 때
병합은 항상 인접한 두 파일만 가능하며, 병합 순서에 따라 총 비용이 달라진다.

1. ((a + b) + c) + d
   • a + b → ab = 40 + 30 = 70
   • ab + c → abc = 70 + 30 = 100
   • abc + d → abcd = 100 + 50 = 150

=> 70 + 100 + 150 = 320

2. (a + (b + c)) + d
   • b + c → bc = 30 + 30 = 60
   • a + bc → abc 40 + 60 = 100
   • abc + d → abcd = 100 + 50 = 150

=> 60 + 100 + 150 = 310

3. a + ((b + c) + d)
   • b + c → bc = 30 + 30 = 60
   • bc + d → bcd = 60 + 50 = 110
   • a + bcd → abcd = 40 + 110 = 150

=> 60 + 110 + 150 = 320

4. a + (b + (c + d))
   • c + d → cd = 30 + 50 = 80
   • b + cd → bcd = 30 + 80 = 110
   • a + bcd → abcd = 40 + 110 = 150

=> 80 + 110 + 150 = 340

5. (a + b) + (c + d)
   • a + b → ab = 40 + 30 = 70
   • c + d → cd 30 + 50 = 80
   • ab + cd → abcd = 70 + 80 = 150

=> 70 + 80 + 150 = 300

결과적으로 5가지 방법 중 최소 비용인 300을 구하는 것이 문제의 목표이다.

결과과 최적의 경우일 때, 이전결과들도 최적의 경우여야 한다는 점에서 DP알고리즘을 떠올릴 수 있다.

dp[start][end]의 값에 start번 파일부터 end번 파일을 하나로 합칠 때 필요한 최적,최소의 비용을 저장한다.
점화식은 다음과 같이 정의할 수 있다.
dp[i][j] = min(MIN, dp[i][k] + dp[k+1][j]) + sum(i~j))

그리고 결국의 마지막에는 a번부터 d까지 다 더한 값을 더해줘야하므로 누적합을 저장하는 배열을 만들어 활용하면 더 시간이 단축될 수 있다.

• 또한 누적합배열을 저장해놓으면 i~j 구간합을 prefix[j] - preifx[i-1] 로 구할 수 있음을 잊지말자.

해답 및 풀이

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    # 파일의 개수 K
    K = int(sys.stdin.readline())

    # 파일 배열 File
    File = [0] + list(map(int, sys.stdin.readline().split())) # 파일 크기들을 1-based로 만들기 위해 앞에 0을 하나 붙임
    
    # 누적합 배열 Sum[i]는 File[1]부터 File[i]까지의 합
    Sum = [0] * (K + 1)
    for i in range(1, K + 1):
        Sum[i] = Sum[i - 1] + File[i]

    # dp[i][j]: i번부터 j번 파일을 합칠 때 드는 최소 비용
    dp = list([0] * (K + 1) for _ in range(K + 1))
    
    #cnt는 start와 end의 차이로 count가 1이면 파일 2개를 합치는 것을 의미하고, 2이면 파일 3개를 합치는 것을 의미
    for cnt in range(1, K):
        for start in range(1, K - cnt + 1): # 구간이 범위를 넘어가지 않게 처리 (cnt의 마지막 요소가 파일의 범위인 K안에 있어야 하므로)
            end = start + cnt

            MIN = sys.maxsize # = 굉장히 큰 값
            for mid in range(start, end):
                MIN = min(MIN, dp[start][mid] + dp[mid + 1][end])

            dp[start][end] = MIN + Sum[end] - Sum[start - 1]
            # 누적합[j] - 누적합[i-1] 은 i부터 j까지의 부분합!
            
    print(dp[1][K])

dp 확실히 어렵다.

핵심 로직은 다음과 같았다.

파일을 다 합치려면 여러 번 나눠서 합쳐야 함
어디서 나눌지(mid)를 결정하면서 가장 효율적인 병합 경로를 찾는 과정
그래서 dp[start][end]를 구하기 위해
dp[start][mid]와 dp[mid+1][end]를 반복적으로 쪼개보고
모든 경우의 수 중 최소를 구하는 것

https://developer-project.tistory.com/485
게시글을 참고하여 공부하고 포스팅했다.