[백준 1715번] 카드 정렬하기 (Python/파이썬)

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

1715번: 카드 정렬하기

섞는 횟수를 최소로 하기 위해서는 가장 적은 묶음 끼리 더하면서 카드를 합해야 횟수를 최소로 할 수 있다.

최소묶음 끼리 더하면 되기 때문에 최소값을 다루기 쉬운 우선순위큐 heapq 모듈을 이용하여 문제를 해결 할 수 있다.

최소묶음끼리 더하고, 나온 묶음을 다시 heappush하고, 다시 최소묶음끼리 더하고 ... 반복하면 끝!

코드는 다음고 같다.

 

import sys
import heapq
input = sys.stdin.readline

def Sol():
  N = int(input())
  Card = []

  for _ in range(N):
    heapq.heappush(Card, int(input()))

  total = 0
  cnt = 0
  while len(Card) > 1:
    c1, c2 = heapq.heappop(Card), heapq.heappop(Card)
    cnt = c1 + c2
    total += cnt
    heapq.heappush(Card,cnt)
  print(total)

if __name__ == "__main__":
  Sol()

 

 

 

 

 

 

 

글이나 코드에 대한 조언 모두 환영합니다!