boj.kr/1715 카드 정렬하기 (gold4) 파이썬 풀이

이전의 비교횟수 목록과 남아있는 카드개수 목록 중 매번 최소값을 선택할 수 있어야 한다.

 

1. heapq를 import

2. N개의 card를 cards 배열에 모두 저장

3. cards 의 요소가 2개 이상이라면, cards에 요소가 하나만 남을 때가지 아래를 반복

3.1. heapq.heappop을 사용해 최소값을 두번 꺼내기

3.2. tot 변수에 두 최소값의 합을 더하기

3.3. cards에 두 최소값의 합을 heapq.heappush 하기

4. tot 변수 값을 출력

 

import heapq
N = int(input())

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

tot = 0
if N > 1:
    while len(cards) > 1:
        a = heapq.heappop(cards)
        b = heapq.heappop(cards)
        tot += (a+b)
        heapq.heappush(cards, (a+b))

print(tot)

 

heapq를 사용하면 매번 최소값을 heappop으로 꺼내올 수 있다.