파일 합치기 3

• 파일 합치기 1, 2, 4는 동일한 문제를 n의 범위만 다르게 한 것이지만, 이 문제는 문제 자체가 살짝 다르다. 다른 파일 합치기들은 인접한 파일들만 합칠 수 있어서 결국 최적 이진 검색 트리문제와 동일한 문제가 되지만, 이 문제에서는 인접하지 않은 파일들끼리도 합칠 수 있다.
• 인접하지 않은 파일들끼리도 합칠수 있다면, 그리디한 방식으로 해결 가능한다. 매 단계에서 가장 크기가 작은 파일 두개를 골라서 합치는 것을 반복하면 된다. huffman coding을 만드는 것과도 동일한 문제이다.
• 크기가 작은 파일 두개를 골라서 합치는 것은, 우선 순위 큐를 이용해서 빠르게 처리가능하다. extract_min을 두번 하고, 더한 값을 insert하면 O(logn)에 처리할 수 있고, 이것을 n-1번 해야 하므로 총 시간 복잡도는 O(nlogn).

"""Solution code for "BOJ 13975. 파일 합치기 3".

- Problem link: https://www.acmicpc.net/problem/13975
- Solution link: http://www.teferi.net/ps/problems/boj/13975
"""

import heapq


def main():
    T = int(input())
    for _ in range(T):
        K = int(input())  # pylint: disable=unused-variable
        file_sizes = [int(x) for x in input().split()]

        cost = 0
        heapq.heapify(file_sizes)
        while True:
            try:
                f1 = heapq.heappop(file_sizes)
                f2 = heapq.heappop(file_sizes)
                cost += f1 + f2
                heapq.heappush(file_sizes, f1 + f2)
            except IndexError:
                break

        print(cost)


if __name__ == '__main__':
    main()