[BOJ] #1715 - 카드 정렬하기

1715번: 카드 정렬하기

 

 

** 문제 유형

• 힙, 자료구조, 그리디

 

** 풀이

1. 가장 크기가 작은 숫자 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적음
   • (10, 20, 40) ---30---> (30, 40) ---70---> (70)
   • (40, 10, 20) ---50---> (50, 20) ---70---> (70)
2. 가장 크기가 작은 숫자 카드 묶음들을 2개씩 합치기 위해, 힙 자료구조를 이용

 

import heapq

n = int(input())

heap = []
rslt = 0

for _ in range(n):
    data = int(input())

    heapq.heappush(heap, data) # 최소 힙 구조

while len(heap) != 1: # 힙에 원소가 1개 남을 때까지
    first = heapq.heappop(heap) # 가장 작은 수부터 꺼냄
    second = heapq.heappop(heap)

    heapq.heappush(heap, first + second)
    rslt += first + second
    
print(rslt)