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

1. 문제 링크

https://www.acmicpc.net/problem/13975

13975번: 파일 합치기 3

 

2. 문제 요약

두 개의 파일을 계속 합하여 최종적으로 하나의 파일을 완성하는데 필요한 비용의 총합을 구한다.

 

3. 아이디어 정리

1. 우선순위 큐 최소힙을 이용하여 가장 작은 2개의 파일을 얻는다.
2. 두 파일을 합하여 다시 최소 힙에 넣고 파일이 1개가 될 때까지 진행한다.

 

4. 문제 풀이

4-1. 내 풀이

import sys
import heapq

for _ in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    heapq.heapify(arr)   # 최소힙
    result = 0
    # 가장 작은 2개의 파일 크기를 꺼내서 합친값을 다시 우선순위 큐에 넣기 
    while len(arr) >= 2:
        f = heapq.heappop(arr)
        s = heapq.heappop(arr)
        result += (f + s)
        heapq.heappush(arr, (f + s))
    print(result)

 

5. 결론

• 우선순위 큐(최소힙) 이용한 문제