[백준][파이썬] 1715번. 카드 정렬하기

문제

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

 

풀이

최소한의 비교를 하기 위해서는, 항상 가장 작은 카드 묶음 2개씩을 비교해야 한다.

그렇기 때문에 최소 힙을 이용하여 구현하였다.

import heapq

N = int(input())
card = []
for _ in range(N) :
  heapq.heappush(card, int(input()))

if N == 1 :  # 카드 묶음이 1개라면 비교할 필요 없음
  print(0)
else :
  answer = 0
  while True :
    if len(card) == 1 :
      break
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    answer += (n1 + n2)  # 가장 작은 카드 묶음 2개 더하기
    heapq.heappush(card, n1 + n2)
  print(answer)