[백준] 1715번 - 카드 정렬하기

문제 분석

문제를 통해 알 수 있듯 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교횟수를 줄일 수 있는 방법임을 알 수 있다. 이때, 더한 값을 다시 저장할때마다 정렬이 일어나야 하므로 우선순위 큐를 이용해서 해결하면 된다.

소스 코드

# 카드 정렬하기

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
q = PriorityQueue()
compareCnt = 0

for _ in range(N):
    q.put(int(input()))

while q.qsize():
    if q.qsize() == 1:
        print(compareCnt)
        break
    else:
        first = q.get()
        second = q.get()
        compareCnt += first + second
        q.put(first + second)