[코드트리] greedy, 숫자 합치기(우선순위Heap)

heapq 라이브러리

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함

 

https://www.codetree.ai/missions/8/problems/%08merge-numbers/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

import heapq
n=int(input())
arr=list(map(int,input().split()))

heapq.heapify(arr)
answer=0
while len(arr)>1:
    x = heapq.heappop(arr)
    y = heapq.heappop(arr)
    heapq.heappush(arr,x+y)
    answer += x+y


print(answer)