파이썬 백준 1715 카드 정렬하기

import sys   input = sys.stdin.readline import heapq n = int(input()) l = [] sum = 0 for i in range(n) :     c = int(input())     heapq.heappush(l, c) for i in range(n-1) :     a = heapq.heappop(l)     b = heapq.heappop(l)     sum = sum + a + b     heapq.heappush(l, a + b) print(sum)

a와 b를 합친 덱을 또다른 덱 c와 정렬할 때는 a와 b가 모두 카운트된다.

즉 매수가 많은 덱은 가능한 한 늦게 합쳐야 덜 카운트되고, 이는 항상 가장 적은 둘을 합쳐야 함을 의미한다.

받은 리스트를 힙의 형태로 정리하여 2번의 pop으로 최솟값을 뽑은 뒤 둘의 합을 힙에 다시 넣어준다.

이를 n-1번 반복하면 마지막으로 다 합친 덱이 남고, 그때까지 카운트한 sum이 답이 된다.