백준 13975. 파일 합치기 3

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

13975번: 파일 합치기 3

 

코드

import heapq
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    k = int(input())
    num = list(map(int, input().split()))
    heap = []
    total = 0

    for n in num:
        heapq.heappush(heap, n)

    while True:
        if len(heap) == 1:
            break
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        s = a + b
        total += s
        heapq.heappush(heap, s)

    print(total)

 

문제를 읽고 어떻게 해야

필요한 비용을 최소로 할 수 있을 지에 대한

고민이 좀 길었던 것 같다.

 

주어진 문제 예시의 첫 번째 테스트 케이스를 보면서

오름차순 정렬 후에 가장 큰 수와 작은 수를 더해주면 되나 싶었지만,

근거 없는 추측이었고 해답도 아니었다.

 

주어진 예시를 보면서 다시 생각해 보니까

비용이 최소가 되기 위해서는

더해지는 비용들이 최소가 되어야 하는데

더해지는 비용이 최소가 되기 위해서는

파일을 합칠 때마다 최소 비용이 드는 합치기를 수행해야 했다.

 

따라서 생각한 해법은

가장 작은 2개의 수를 합치고

그 합친 값을 다시 숫자 리스트에 넣어서

정렬을 하고 또 가장 작은 2개의 수를 합치고...

이 과정을 반복하면 되는 것이었다.

 

수행 속도를 고려해 heapq를 사용했다.

백준에서 채점 속도가 매우 느렸지만 통과는 됐다.