Baekjoon 11066. 파일 합치기 / Python

11066. 파일 합치기

난이도 : 골드 3
소요 시간 : 30분
날짜 : 2025.01.09
언어 : 파이썬
알고리즘 유형 : dp

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 파일 크기 배열이 주어진다.
2. 파일을 두 개씩 골라서 합칠 수 있다.
3. 두 파일은 합쳐지면 크기가 더해지며 하나가 되고, 합치는데에는 두 파일의 크기의 합이 비용으로 든다.
4. 최소 비용으로 파일을 하나로 합치기

2. 해결 방식

1. DP배열 : dp[i][j] = i부터 j까지 합치는데 필요한 최소 비용
2. prefix_sum(누적합)을 이용해서 좀 더 효율적인 구현을 했다.
3. 점화식
   • dp[i][i] 는 0이다.
   • dp[i][i+1] 은 두 파일 크기의 합이다.
   • dp[i][j] 는 i~j 사이에 어떤 수 p가 있다고 가정했을 때, p를 기준으로 왼쪽 오른쪽을 합치는 것들의 최솟값이 된다.
   • 즉, dp[i][p] + dp[p+1][j]들의 최솟값을 구하면 된다.
   • 최솟값을 구해준 후에는, 다시 크기만큼의 비용인 i~j까지의 누적합을 더해주어야만 한다.

3. 정답 코드

import sys;input = sys.stdin.readline

inf = float('inf')

def sol(arr:list, k:int):
    prefix_sum = [0] * (k + 1)
    for i in range(k):prefix_sum[i+1]=prefix_sum[i]+arr[i]   # 누적합

    dp = [[0] * k for _ in range(k)]    # dp[i][j] : i부터 j까지 합치는 최솟값
    for i in range(k-1):dp[i][i+1] = arr[i]+arr[i+1]    # 크기 두개짜리 합치기

    for l in range(2, k):  # 구간의 길이
        for i in range(k - l):  # 시작점
            j = i + l   # 끝점
            dp[i][j] = inf
            dp[i][j] = min(
                [inf] + 
                [dp[i][p] + dp[p+1][j] for p in range(i, j)]
            ) + prefix_sum[j + 1] - prefix_sum[i]

    print(dp[0][k-1])


for _ in range(int(input())):
    k = int(input())
    arr = list(map(int, input().split()))
    sol(arr, k)