파이썬) 백준 알고리즘 | 13975번 : 파일 합치기 3

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

13975번: 파일 합치기 3

 

풀이

파일을 heap에 넣고 가장 작은 두 개를 빼고 더해서 다시 heap에 넣어줍니다.

그 과정에서 더한 값은 cnt에 더해주고 마지막에 cnt를 출력해주면 됩니다.

 

import heapq

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    cnt = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        cnt += (a+b)
        heapq.heappush(heap, a+b)
    print(cnt)