[백준][Python] 13975번 파일 합치기 3

13975번: 파일 합치기 3

 

코드

import heapq
import sys 

t = int(input())
for _ in range(t):
    k = int(input())
    n_list = list(map(int,sys.stdin.readline().split()))
    
    heapq.heapify(n_list)
    if k == 1:
        print(n_list[0])
        break
    answer = 0
    while len(n_list)>1:
        a = heapq.heappop(n_list)
        b = heapq.heappop(n_list)
        sum = a+b
        answer+=sum
        heapq.heappush(n_list,sum)
    print(answer)

 

설명

우선 주어진 수 중에서 가장 작은 수를 먼저 더해야 최소 비용을 구할 수 있다. 그래서 힙을 이용해서 작은 수가 먼저 pop 될 수 있게 했다.

먼저 입력 값을 리스트로 받은 후 heapify를 이용해서 힙 자료형으로 변환할 수 있었다. 

가장 작은 값 두 개씩 힙에서 꺼내서 더해준 뒤 그 값을 answer에 더해주고 다시 힙에 넣는다. 이걸 반복하게 되면 마지막에는 힙에 숫자 하나만 남게 되기 때문에 while문의 조건을 n_list의 길이가 1일 때 빠져나가는 것으로 했다.