백준 5014 카드 정렬하기

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

1715번: 카드 정렬하기

📌 해결 과정

heap 자료구조의 장점을 정말 잘 느낄수 있는 문제이다.

 

먼저, 그리디 방식으로 이 문제에 접근해보면

비교횟수의 최솟값을 구해야 하므로 언제 비교횟수가 크게 증가하는지에 대해 생각해볼 필요가 있다.

카드 수가 많은 묶음일수록 최대한 마지막에 비교할 수 있도록 해야한다

 

예를 들어서,

묶음의 수 : 6

각 묶음에 속한 카드 : [20, 30, 40, 50, 60, 80]

 

card_list	compare_cnt
20 30 40 50 60 80	0
40 50 50 60 80	50
50 60 80 90	50 + 90
80 90 110	50 + 90 + 110
110 170	50 + 90 + 110 + 170
280 (모든 카드 묶음의 비교가 끝나고 하나의 묶음이 됨)	50 + 90 + 110 + 170 + 280 = 700

두 묶음의 카드의 비교를 마치면 두 묶음의 카드는 하나의 묶음으로 합쳐지기 때문에 다음에 비교할 묶음에 속하는 카드 수 보다 많다면 나중에 비교할 수 있도록 해줘야 한다.

 

📌 코드

import heapq
import sys

input = sys.stdin.readline

n = int(input())
card_list = []
compare_cnt = 0

for _ in range(n):
    heapq.heappush(card_list, int(input()))
# 카드 묶음이 하나라면 비교할 필요가 없으므로 0을 출력한다.
if len(card_list) == 1:
    print(0)
else:
    while len(card_list) > 1:
        comp1 = heapq.heappop(card_list)
        comp2 = heapq.heappop(card_list)
        compare_cnt += comp1 + comp2

        heapq.heappush(card_list, comp1 + comp2)

    print(compare_cnt)