[Python] 백준 1715 카드 정렬하기

 

문제 분석

• 정렬된 두 묶음의 숫자 카드
• 각 묶음의 카드 수를 A, B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다.

 

코드 설계

• 작은 것끼리 묶어 나가는 것이 가장 효율적이다.
• 우선순위 큐

 

정답 코드

import sys
input = sys.stdin.readline
import heapq

n = int(input())
bundle = [int(input()) for _ in range(n)]
heapq.heapify(bundle)
ans = 0

# 이전에 더한거 누적 + 새로 합
while len(bundle) > 1: # 2개 남았을 때까지
    min_1 = heapq.heappop(bundle)
    min_2 = heapq.heappop(bundle)
    ans += min_1+min_2
    heapq.heappush(bundle, (min_1+min_2))

print(ans)