테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 파일 합치기 3 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}