파일 합치기

• 최적 이진 검색 트리 문제이다. 자세한 내용은 링크 참조.
• 링크에서 설명했듯이, O(n^3) 풀이를 의도한 문제이지만, 그렇게 풀어서는 Python으로는 통과가 힘들다. 여기에서는 크누스 최적화를 적용하여 O(n^2)에 풀었다.
• Garsia–Wachs algorithm 을 이용하면 O(nlogn)에도 해결이 가능하고, O(n^2)으로 구현해도 이 방식보다 빠르다. Garsia–Wachs algorithm의 O(n^2)의 구현은 파일 합치기 2 를 참조

"""Solution code for "BOJ 11066. 파일 합치기".

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


def main():
    T = int(input())
    for _ in range(T):
        K = int(input())
        file_sizes = [int(x) for x in input().split()]

        v = 0
        prefix_sum = [v] + [v := v + x for x in file_sizes]
        dp = [[0] * K for _ in range(K + 1)]
        opt = list(range(K))
        for l in range(1, K):
            for i in range(K - l):
                j = i + l
                dp[i][j], opt[i] = min((dp[i][k] + dp[k + 1][j], k)
                                       for k in range(opt[i], opt[i + 1] + 1))
                dp[i][j] += prefix_sum[j + 1] - prefix_sum[i]

        print(dp[0][K - 1])


if __name__ == '__main__':
    main()