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

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

 

# 백준 13975 파일 합치기 3
# 여러 개의 파일을 두 개씩 합치며 전체 최소 비용을 구하는 문제
# 최소 힙을 사용하여 매번 가장 작은 두 파일을 합치는 전략 (그리디 알고리즘)

import heapq, sys
input = sys.stdin.readline

T = int(input())  # 테스트 케이스 수

for _ in range(T):
    ans = 0  # 총 합치는 데 드는 비용

    K = int(input())  # 파일 개수
    hq_files = list(map(int, input().split()))  # 각 파일 크기 입력
    heapq.heapify(hq_files)  # 최소 힙 구성

    while hq_files:
        f1 = heapq.heappop(hq_files)  # 가장 작은 파일 꺼냄

        if hq_files:
            f2 = heapq.heappop(hq_files)  # 그 다음으로 작은 파일 꺼냄
        else:
            break  # 파일이 하나만 남은 경우 합칠 필요 없음

        merge_f = f1 + f2  # 두 파일을 합치고
        ans += merge_f  # 누적 비용에 더함
        heapq.heappush(hq_files, merge_f)  # 합친 파일을 다시 힙에 추가

    print(ans)  # 테스트 케이스 결과 출력

 

우선순위 큐인 HEAPQ를 사용하여 해결하였다.