[BOJ] 1715번: 카드 정렬하기 (파이썬)

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

1715번: 카드 정렬하기

---

보유하고 있는 카드 묶음 중에 가장 작은 두 개의 묶음을 비교해야 최소 횟수로 비교할 수 있습니다.

 

첫번째 원소가 항상 제일 작은 값이 되도록 유지하는 heapq 라이브러리를 사용합니다. 비교가 필요한 카드 묶음을 heapq에 넣어 관리합니다.

가장 작은 묶음과 그 다음으로 작은 묶음을 꺼내어 비교하고, 하나가 된 카드 묶음을 다시 heapq에 넣습니다.

카드 묶음이 1개 남을 때까지 반복합니다.

 

import sys
import heapq

n = int(sys.stdin.readline().strip())
deck = [int(sys.stdin.readline().strip()) for _ in range(n)]

if len(deck) == 1:
    print(0)
else:
    answer = 0
    heapq.heapify(deck)
    while len(deck) > 1:
        first = heapq.heappop(deck)
        second = heapq.heappop(deck)
        current = first + second
        answer += current
        heapq.heappush(deck, current)
    print(answer)