백준 11066 - 파일 합치기 (파이썬)

Answer

import sys
input = sys.stdin.readline

for i in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    dp = [[0] * (n + 1) for i in range(n + 1)]
    
    for i in range(n - 1):
        dp[i][i + 1] = a[i] + a[i + 1]
        for j in range(i + 2, n):
            dp[i][j] = dp[i][j - 1] + a[j]

    for i in range(2, n):
        for j in range(n - i):
            k = j + i
            dp[j][k] += min([dp[j][l] + dp[l + 1][k] for l in range(j, k)])
    
    print(dp[0][n - 1])