[BOJ] Q1715 카드 정렬하기

[BOJ] Q1715 연구소

Question

Language: Python

Difficulty: Gold 4

카드를 서로 비교하면서 매번 합쳐나갈 때, 이때 비교회수의 최소값을 구하는 문제이다.

그럼 그냥 정렬을 한 후 앞에서 부터 비교를 하면 되는 것 아닌가?

예시

data=[10,10,10,10] 

|순서| 리스트| 비교횟수| |:—|:—- |:—— | |1|[20,10,10]|(10+10)| |2|[30, 10] |20 + (20+10)| |3|[]|50 + (30+10) |

총 비교회수는 90번이다. 하지만 이는 최소가 아니다…

순서	리스트	비교횟수
1	[10,10,20]	(10+10)
2	[20,20]	20 + (10+10)
3	[]	40 + (20+20)

최소값은 80번이다.

비교를 할때는 항상 제일 작은 2개의 카드 뭉치를 이용 해야한다. 즉, 중간 비교를 하고 카드를 합친 후, 카드 뭉치를 넣고 정렬을 새로 수행해야한다. 이를 위해 항상 배열에서 넣고 뺄 때, 정렬을 매번 수행하는 heapsort을 활용한다.

Solution

import heapq
data=[]
n=int(input())
for _ in range(n):
    heapq.heappush(data,int(input()))

sub_sum=0
while len(data)>=2:
    result=heapq.heappop(data)+heapq.heappop(data)
    sub_sum+=result
    heapq.heappush(data,result)
print(sub_sum)