백준 1715번 : 카드 정렬하기

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

1715번: 카드 정렬하기

 

N개 만큼의 카드묶음이 있으며 이들 중 2개를 골라 1개의 카드묶음으로 만드는 작업을 수행할 수 있고 최종적으로 N개의 카드묶음을 1개의 카드묶음으로 만드려고 한다. 2개의 카드묶음을 합칠 때에는 각 카드묶음에 있는 카드 수를 합한 만큼 비교를 수행하는데, 비교 횟수를 최소화하려고 한다. 이때 최소화된 비교 횟수를 구하는 문제이다. 

 

전형적인 그리디 알고리즘 유형이다. N개의 카드묶음을 합쳐서 1개로 만들기 위해선 총 N-1번의 비교를 수행해야한다. 최종적으로 비교해야 하는 횟수는 변하지 않기 때문에 매번 비교를 수행할 때마다 카드묶음들 중에서 카드 수가 가장 적은 2개의 묶음을 합치면 최소한의 비교로 합칠 수 있다. 합쳐서 만들어진 카드묶음 역시 나중에 다른 카드묶음과 합쳐지기 때문에 카드 수가 적을수록 이득이다. 

 

위 아이디어를 구현하기 위해서 우선순위 큐를 사용했다. 입력으로 주어지는 카드묶음들을 큐에 넣고, 카드 수가 가장 적은 2개의 카드묶음을 큐에서 꺼내어 각 카드묶음의 카드 수를 합한 값을 다시 큐에 넣어준다. 카드묶음을 합치는 과정을 수행할 때 마다 3logN만큼의 시간이 소요된다. 이 과정을 N-1번 수행해야 하므로 총 걸리는 시간은 O(3(N-1)logN) = O(NlogN) 이다. 

 

import sys
import heapq
input = sys.stdin.readline

s = [int(input()) for _ in range(int(input()))]
heapq.heapify(s)
r = 0

while len(s) > 1:
    c = heapq.heappop(s) + heapq.heappop(s)
    r += c
    heapq.heappush(s, c)
print(r)