우선 순위 큐

카드 정렬하기

두 묶음씩 골라서 서로 합쳐 나갈 때 가장 최소한의 비교를 위해서는 더하는 숫자들이 가장 작아야한다.
그래서 나는 숫자들이 있는 카드 묶음이 계속 작도록 갱신했다.
예를 들어 30, 40, 50 , 60 이 있다고 치면,
먼저 30, 40을 큐에서 빼고 둘의 합을 결과값에 더해주고 이를 다시 큐에 넣는 작업을 반복하면 된다.
그러면 50, 60 70 이 남으니까 50, 60을 빼서 둘의 합을 다시 결과값에 넣어주고 이를 다시 큐에 넣는다.
그러면 60 110 이 남았으니 이를 더한 값을 또 결과값에 넣어준다.
그러면 카드 묶음을 모두 더했으니 이제는 결과값을 반환하면 된다.

import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
	lst.append(int(input()))
   # 값이 작은 순으로 정렬
lst.sort()
result = 0
# 리스트를 갱신하기 위해 가장 작은 두 값을 빼서 결과값에 더하고 다시 큐에 넣는다 
for i in range(len(lst)-1):
	x = heapq.heappop(lst)
	y = heapq.heappop(lst)
	result += (x+y)
	heapq.heappush(lst, x+y)
print(result)