파일 합치기

1. 개요

• https://www.acmicpc.net/problem/11066

2. 풀이

import sys

def solution():
    # 입력함수
    INPUT = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(INPUT())
    READINTLIST = lambda: list(map(int, INPUT().split()))
    UNDIFINED = -1
    
    def answers():
        results = []

        for _ in range(READINT()):
            results.append(answer(READINT(), READINTLIST()))
        return "\n".join(map(str, results))
    
    def answer(n, datas):
        DB = [[UNDIFINED]*n for _ in range(n)]
        SUM = [0]*(n+1)
        
        for i in range(n):
            DB[i][i], SUM[i+1] = 0, datas[i]

        for i in range(1, n+1):
            SUM[i] += SUM[i-1]

        # bottom up 방식의 dp로 pypy3로 통과
        for width in range(1, n):
            for start in range(n-width):
                
                end = start+width
                candidates = []
                
                for mid in range(start, end):
                    candidates.append(DB[start][mid]+DB[mid+1][end])

                DB[start][end] = min(candidates)+SUM[end+1]-SUM[start]

        return DB[0][-1]

    return answers()
    
print(solution())