Category
알고리즘  그리디

[1715] 카드 정렬하기

by Hwang

문제

https://www.acmicpc.net/problem/1715

풀이

카드를 묶음을 합치는 횟수를 생각해보았을 때 어떠한 방식으로 묶음을 합쳐가든 횟수는 동일합니다.

따라서 비교의 수를 최소로 하기 위해서는 현재 존재하는 가장 카드의 개수가 작은 두 개의 묶음을 합치는 방식으로 하면 되겠다고 생각이 되었습니다.

저는 최소 힙을 이용해서 가장 작은 두 묶음을 뽑아주는 방식으로 풀이했습니다.

import sys
import heapq

N = int(sys.stdin.readline())
heap = []
result = 0
for _ in range(N):
    bundle = int(sys.stdin.readline())
    heapq.heappush(heap, bundle)
while len(heap) > 1:
    bundle1 = heapq.heappop(heap)
    bundle2 = heapq.heappop(heap)
    merge = bundle1 + bundle2
    result += merge
    heapq.heappush(heap, merge)
print(result)


 Comment