백준 1715 [카드정렬하기] 파이썬

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

# 백준 1715 카드 정렬하기
# 여러 묶음의 숫자 카드를 효율적으로 정렬하는 최소 비용 계산
# 항상 가장 작은 두 묶음을 먼저 합치면 전체 비용이 최소가 됨 (그리디 + 최소 힙 사용)

import heapq, sys
input = sys.stdin.readline

ans = 0  # 총 비용을 저장할 변수
N = int(input())  # 카드 묶음의 개수
hq_cards = []

# 카드 묶음의 크기를 입력 받아 리스트에 저장
for _ in range(N):
    hq_cards.append(int(input()))

heapq.heapify(hq_cards)  # 리스트를 최소 힙 구조로 변환

# 카드 묶음이 2개 이상 남아 있는 동안 반복
while hq_cards:
    # 가장 작은 두 카드 묶음을 꺼냄
    c1 = heapq.heappop(hq_cards)
    if hq_cards:
        c2 = heapq.heappop(hq_cards)
    else:
        break  # 하나만 남았다면 종료

    merge_c = c1 + c2  # 두 카드 묶음을 합치는데 드는 비용
    ans += merge_c  # 누적 비용에 더함

    heapq.heappush(hq_cards, merge_c)  # 합쳐진 묶음을 다시 힙에 넣음

print(ans)  # 최종 최소 비용 출력

 

 

https://www.acmicpc.net/problem/13975 문제와 마찬가지로 우선순위 큐를 이용하여 해결하였다.