[백준] 13975 파일 합치기 3 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/13975
• 🔑 우선순위 큐, 최소 힙
  • 파일의 크기가 가장 작은 두 개를 골라서 하나의 파일로 합친다.
    • 이 과정을 위해 힙을 사용
  • 이때 드는 비용을 더한다.
  • 합쳐진 파일을 다시 힙에 넣는다.
  • 힙에 들어있는 파일이 1개가 될 때까지 반복하면 끝 ✨

 

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    k = int(input())
    file = list(map(int, input().split()))
    heapify(file)
    answer = 0

    while len(file) >= 2:
        x = heappop(file)
        y = heappop(file)
        answer += x + y
        heappush(file, x+y)
        
    print(answer)