[백준] 13975번: 파일 합치기 3

문제

백준 - 13975번: 파일 합치기 3

분석

여러 장(chapter)에 대한 파일 크기 정보들이 주어지고, 두 파일씩 합쳐서 최종적으로 하나의 파일로 합치려고 할 때, 필요한 최소비용을 계산하는 문제이다.

우선순위 큐를 하나 두고 초기에 모든 파일 크기 정보를 넣는다.
가장 작은 두 파일을 하나로 합쳐서 우선순위 큐에 다시 넣는다.
이렇게 파일 개수가 1개가 될 때까지 반복하면 최소비용을 구할 수가 있다.
주의할 점은 우선순위 안에 있는 것은 파일 크기이므로 마지막에 남은 것은 최종 파일 크기이다.
비용은 누적되어서 계산하기 때문에 따로 변수를 둔다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from heapq import heapify, heappush, heappop

t = int(input())
for _ in range(t):
    k = int(input())
    pq = list(map(int, input().split()))
    heapify(pq)
    cost = 0
    while len(pq) > 1:
        a = heappop(pq)
        b = heappop(pq)
        heappush(pq, a+b)
        cost += a+b
    print(cost)

끝으로..

우선순위 큐 개념을 복습할 수 있던 좋은 문제였다.