[백준][DP] 11066. 파일 합치기

11066. 파일 합치기

 

풀이 참고: https://supersfel.tistory.com/entry/11066

• 다른 사람 풀이
  • 한 번에 두 개의 파일만 합칠 수 있고, 파일의 순서는 유지되어야함
  • dp[i][j]: i번째 파일부터 j번째 파일까지 합치는 최소 비용
  • prefix_sum[i]: 1번부터 i번까지의 누적 합 (구간합 빠르게 구하기 위함)
    • [40,30,30] 일때
      • [40,30]+[30]
      • [40]+[30,30]
      • 둘 중에 뭐든 간에 [a,b]+c 의 비용: (a+b) + (a+b)+c 이기 때문에 무조건 a+b+c를 더하게 되어있기 때문
  • 구간 길이를 2,3,... 늘려가며 확인
  • 최종 정답은 dp[1][k] (전체 파일 합치는 최소 비용)

t = int(input())

for _ in range(t):
    k = int(input())
    files = [0] + list(map(int, input().split()))  # 1-based indexing

    # 누적합 계산
    prefix_sum = [0] * (k + 1)
    for i in range(1, k + 1):
        prefix_sum[i] = prefix_sum[i - 1] + files[i]

    # dp[i][j]: i번째 파일부터 j번째 파일까지 합치는 최소 비용
    dp = [[0] * (k + 1) for _ in range(k + 1)]

    for length in range(2, k + 1):  # 부분 파일 길이
        for start in range(1, k - length + 2):  # 시작 인덱스
            end = start + length - 1
            dp[start][end] = float('inf')

            # 중간 지점 q를 기준으로 두 부분으로 나눠서 계산
            for mid in range(start, end):
                cost = dp[start][mid] + dp[mid + 1][end] + (prefix_sum[end] - prefix_sum[start - 1])
                dp[start][end] = min(dp[start][end], cost)

    print(dp[1][k])