백준 1715 카드 정렬하기

문제

• 숫자 카드를 비교하고, 비교한 숫자 카드는 합친다.
• 모든 숫자 카드에 대해 위 과정을 반복한다고 하면, 숫자 카드를 비교한 횟수의 최소값을 구한다.

과정

• 그리디 : 남은 숫자 카드 중 가장 작은 두 카드를 비교하고 합쳐야한다.
  • 카드를 비교할 때마다 비교한 카드 수는 답에 더해지게 된다.
  • 더해지는 수가 작으려면 가장 작은 두 카드를 비교해야 한다.
• 우선순위 큐를 사용해서 남은 카드 중 가장 작은 값을 가진 카드 두 개를 구해야 한다.

import sys
import heapq

N: int = int(input())

ans: int = 0

q = []
for i in range(N):
    inp: int = int(input())
    heapq.heappush(q, inp)

ans = 0

while len(q) >= 2:
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    ans += a + b
    heapq.heappush(q, a + b)

print(ans)