백준 1715 카드 정렬하기 (Python)

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

1715번: 카드 정렬하기

그리디답게 생각하는 데 오래 걸리지 않는다.

해당 카드 뭉치들에서 가장 작은 거 2개를 뽑아오는 것이 가장 최적일 것이다.

 

그러면 가장 작은 뭉치를 어떻게 가져오느냐를 생각해야 하는 데, 당연히 정렬이 먼저 떠오를 것이다.

여기서 퀵 정렬을 사용하면 nlogn의 시간복잡도가 나올 것인데, 지속적으로 가장 작은 것을 가져오려면 우선순위 큐를 사용하는 것이 logn으로 시간복잡도가 더 낮을 것이다.

 

그렇기 때문에 우선순위 큐를 사용하도록 한다.

import sys
import heapq

heap = []

for _ in range(int(sys.stdin.readline().strip())):
    heapq.heappush(heap, int(sys.stdin.readline().strip()))

result = 0

while len(heap) > 1:
    A = heapq.heappop(heap)
    B = heapq.heappop(heap)

    result += (A + B)
    heapq.heappush(heap, A + B)

print(result)

heap이라는 우선순위큐를 만들고 그곳에다가 카드의 수를 입력 받는다.

 

그리고는 while 반복문으로 카드 뭉치가 하나 남을 때까지 카드들을 뭉쳐주고 그렇게 뭉친 카드 뭉치는 다시 우선순위큐로 넣을 수 있도록 한다.