백준 1715 파이썬 (그리디)

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다.

처음에 이 문제를 풀 때 '힙(heap)'이라는 자료구조를 생각해내지 못해서 한참을 헤맸다.

 

이 문제를 풀때 가장 중요한 아이디어는 힙(heap)이라는 생각이다.

 

알고리즘은 이러하다.

0) 총 비교한 횟수(answer)를 0으로 둔다.

1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다.

2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수

3) 두 개를 더한 값을 총 비교한 횟수(answer)에 더해준다.

4) 두 개를 더한 값을 다시 카드 더미(card_deck) 안에 넣는다.

5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다.

(참고. https://claude-u.tistory.com/341)

 

# 1715 카드 정렬하기

import heapq

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


if len(card_deck) == 1: #1개일 경우 비교하지 않아도 된다
    print(0)
else:
    answer = 0
    while len(card_deck) > 1: #1개일 경우 비교하지 않아도 된다
        temp_1 = heapq.heappop(card_deck) #제일 작은 덱
        temp_2 = heapq.heappop(card_deck) #두번째로 작은 덱
        answer += temp_1 + temp_2 #현재 비교 횟수를 더해줌
        heapq.heappush(card_deck, temp_1 + temp_2) #더한 덱을 다시 넣어줌
    
    print(answer)