BOJ 1715 : 카드 정렬하기 (Python)

문제

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

1715번: 카드 정렬하기

 

 

코드

import sys
import heapq
n = int(sys.stdin.readline())

heap = []
for i in range(n):
    heapq.heappush(heap,int(sys.stdin.readline()))

total = 0

if n!=1:
    while len(heap)!=0:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        total += (a+b)
        if len(heap)!=0:
            heapq.heappush(heap,(a+b))

print(total)

 

 

풀이

 

예시에서 10장 20장 40장 묶음이 있으면 (10+20) + (30+40) = 100 번이 최소 비교 횟수라고 했다.

식을 다시 바꾸면 (10+20) + ((10+20)+40) = 100 이다. 이처럼 중복되는 연산이 있으므로 이 부분을 최소화해야 한다. → 중복되는 연산들을 최솟값으로 구성하면 됨

 

그래서 우선 순위 큐(정렬된 원소들을 사용하기 위해)를 이용하여 최솟값끼리 먼저 더한 뒤에 이 더한 값을 다시 우선 순위 큐에 담아서 연산에 활용할 수 있도록 한다.

 

예시)

우선 순위 큐에 10 -> 20 -> 40 으로 담겨 있다고 가정하면

작은 두 값끼리 더한 것(10 + 20 = 30)을 total에 더해준다. 아직 우선 순위 큐 내에 원소가 남아있기 때문에 더한 값을 다시 우선 순위 큐에 넣어서 30 -> 40이 되도록 한다.

 

똑같이 작은 두 값끼리 더한 것(30+40 = 70)을 total에 더해준다.  이제 우선 순위 큐 내에 남아있는 원소가 없으므로 이 total 값이 답이 된다. 

 

위의 과정을 우선 순위 큐 내에 있는 원소 없을 때까지 반복하면 된다.