====== 파일 합치기 2 ======

===== 풀이 =====
  * [[ps:problems:boj:11066|파일 합치기]]에서 n의 제한을 늘린 버전.
  * 풀이는 [[ps:구간 분할 방식에 관한 DP#최적 이진 검색 트리]]를 참고. 여기에서는 Garsia–Wachs algorithm을 적용해서 O(n^2)으로 구현했다. 
  * 크누스 최적화를 사용해서 푼 코드는 [[ps:problems:boj:11066|파일 합치기]]를 참고

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13974. 파일 합치기 2".

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

import itertools
import sys

INF = float('inf')


def insert_rec(size, pos, l):
    cost = 0
    while len(l) + pos > 2 and size >= l[pos - 2]:
        new_size = l.pop(pos - 1) + l.pop(pos - 1)
        new_pos = next(x for x in range(pos - 1, -(len(l) + 1), -1)
                       if l[x] >= new_size) + 1
        cost += new_size + insert_rec(new_size, new_pos, l)
    if pos == 0:
        l.append(size)
    else:
        l.insert(pos, size)
    return cost


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

        l = [INF]
        cost = 0
        for size in itertools.chain(file_sizes, [INF]):
            cost += insert_rec(size, 0, l)

        print(cost)


if __name__ == '__main__':
    main()

</dkpr>
{{tag>BOJ ps:problems:boj:플래티넘_2}}