이번 문제는 그리디 알고리즘을 활용하여 해결하였다. 가장 중요한 포인트는 매번 가장 작은 크기의 파일 두개를 꺼내어 합쳐야만 비용이 최소가 된다는 것이다. 이를 보고 최소힙을 활용하기로 하였다. 파일들을 최소힙에 넣고, 최소힙의 크기가 1보다 클 동안 반복하며 heappop()을 2번 하고, 이 값들을 더하여 결과값에 더하고, 이 값들을 더한 값을 최소힙에 다시 넣었다. 이 과정을 반복하면 결과적으로 파일 1개만 남게되고, 문제가 해결된다.

매번 최솟값을 추출해야 하는 경우: 최소힙 사용
초기에 정렬을 한번만 적용하면 되는 경우: sort()함수 사용

Code

import heapq
t = int(input())
for _ in range(t):
    k = int(input())
    files = list(map(int, input().split()))
    heapq.heapify(files)
    answer = 0
    while len(files) > 1:
        f1 = heapq.heappop(files)
        f2 = heapq.heappop(files)
        answer += (f1 + f2)
        heapq.heappush(files, f1 + f2)
    print(answer)