[BOJ] 1715 - 카드 정렬하기

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

1715번: 카드 정렬하기

import sys
import heapq

n = int(input())

heap = []
for i in range(n):
    data = int(sys.stdin.readline())
    heapq.heappush(heap, data)
    
result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    
    sum = one + two
    result += sum
    heapq.heappush(heap, sum)
    
print(result)

이 문제의 핵심 아이디어는 항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해를 보장한다는 점이다.

따라서 이 문제는 우선순위 큐를 이용한 그리디 알고리즘 유형이라고 볼 수 있다.

 

우선순위 큐를 이용하면 우선순위 큐에 원소를 넣었다 빼는 것만으로도 정렬된 결과를 얻을 수 있다. 따라서 항상 가장 작은 두 개의 값을 꺼내어 그 합을 결과에 더해주고 합을 다시 우선순위 큐에 넣는 것을 반복하면 된다.