[백준] 11066번 파일 합치기 (파이썬)

11066번: 파일 합치기

 

코드

def merge(k, li):
    memo = list([0] * k for _ in range(k))

    for i in range(k - 1):
        memo[i][i + 1] = li[i] + li[i + 1]
        for j in range(i + 2, k):
            memo[i][j] = memo[i][j - 1] + li[j]

    for l in range(2, k):
        for i in range(k - l):
            j = i + l
            minimum = list(memo[i][m] + memo[m + 1][j] for m in range(i, j))
            memo[i][j] += min(minimum)
    return memo[0][k - 1]


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        k = int(input())
        li = list(map(int, input().split()))
        answer = merge(k, li)
        print(answer)