문제 링크 : https://www.acmicpc.net/problem/13975

---

문제 파악

파일을 합치는데 최소 비용을 계산하는 프로그램을 구현해야 한다.

만약 파일이
4, 3, 3, 5 있다면

1. (4+3)+(3+5) 로 합칠 수 있다.
   이 경우에 비용은
   (4+3) + (3+5) + ((4+3) + (3+5)) = 30 이 들고

2. (3+3) + ((4+(3+3)) + ((4+(3+3) + 5) = 31이 들수도 있다.

이 중 30이 더 작으니 답은 30이 된다.
어떤 원리로 최소의 값을 구할 수 있는 걸까?

파일들 중 가장 작은 최소값들을 계속 더해주면 된다.

1 2 3 4 라면
12
12 + 3
123 + 4순으로 말이다.

이 리스트에서 최소값을 뽑아낼때 python에서는 heapq 라는 자료구조를 쓰면 편하다.

이 문제를 풀기위해 알아야 하는 heapq 정보

heapq.heapify(a): 리스트 a를 제자리에서 힙으로 변환. O(N)
heapq.heappop(a): 최솟값 꺼내기. O(log N)
heapq.heappush(a, x): 값 x 넣기. O(log N)

---

해답 및 풀이

import sys
import heapq

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    K = int(input())
    files =list(map(int,input().split())) # 리스트를 힙으로 만들어 줌
    heapq.heapify(files)
    
    result = 0

    # while files:  처음에 이렇게 적었는데 에러가 났다. 원소가 1개 남았을 지라도 두번 pop하기에 오류가 나니까   
    while len(files) > 1 : # 이게 맞다.
        min_1 = heapq.heappop(files)
        min_2 = heapq.heappop(files)

        min_sum = min_1 + min_2
        result += min_sum 

        heapq.heappush(files, min_sum)

    
    print(result)

while 문 작성시 files 가 있을 때동안 돌게 작성했다가 오류가 났다.
왜냐하면 한번 반복문에 두번의 heappop이 이루어지는데 files의 개수가 1이어도 두번 pop 했기 떄문이다.

while len(files) > 1: 로 고쳐주니 통과했다.

리스트에서 최소값을 빼낼때는 heapq 떠올리자