BOJ : 1715 카드 정렬하기

문제 바로가기

우선순위 큐를 이용하면 어렵지 않은 문제.
카드들 중에서 가장 수가 적은 카드 묶음 두개를 합치고, 그 카드들을 다시 우선순위 큐 리스트에 넣어주는 과정을 반복한다. (리스트에 카드가 하나 남을때까지)

import sys
import heapq
input = sys.stdin.readline

n = int(input())
cards = [int(input()) for _ in range(n)]
heapq.heapify(cards)

sum = 0

while len(cards) > 1:
    a,b = heapq.heappop(cards), heapq.heappop(cards)
    sum += a + b
    heapq.heappush(cards, a + b)

print(sum)