출쳐 |https://www.acmicpc.net/problem/1715

코드

import heapq

n = int(input())
card = []

for _ in range(n):
    num = int(input())
    heapq.heappush(card,num)

rs = 0

while len(card) > 1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    rs += n1+n2
    heapq.heappush(card,n1+n2)
print(rs)

코드설명

먼저 해당 문제를 풀기 전 우선순위 큐에 대해서 알아야 된다.

해당 사이트를 참고하면 된다. 필자는 해당 부분을 다시 복습했다.

• n1 = heapq.heappop(card): card 리스트에서 가장 작은 값을 최소 힙에서 꺼내어 변수 n1에 저장한다.

• n2 = heapq.heappop(card): 다시 card 리스트에서 가장 작은 값을 꺼내어 변수 n2에 저장한다.

• rs += n1 + n2: n1과 n2를 더한 값을 rs에 누적한다. 이 값은 카드 묶음을 합친 비용을 나타낸다.

• heapq.heappush(card, n1 + n2): n1과 n2를 합친 값을 다시 card 리스트에 추가한다.