[BOJ] Q11066 파일 합치기

[BOJ] Q11049 파일 합치기

Question

Language: Python

Difficulty: Gold 3

해당 문제는 Q11049 와 비슷한 유형의 문제로 아래의 행렬곱을 파일 합치기로 바꿔주면 된다.

A1,A2,A3,A4가 있을 때 (A1),(A2,A3,A4) = A1-A1의 임시 파일 개수 + A2-A4 임시 파일 개수+ A1-A4 파일 개수 (A1,A2),(A3,A4) = A1-A2의 임시 파일 개수 + A3-A4 임시 파일 개수+ A1-A4 파일 개수 (A1,A2,A3),(A4) = A1-A3의 임시 파일 개수 + A4-A4 임시 파일 개수+ A1-A4 파일 개수

을 비교해서 최소 횟수를 구해야한다.

추가로 누적합 개념을 활용해서 반복되는 합 연산을 최소화한다.

Solution

from math import inf
def solution():
    dp=[[0] * (num) for _ in range(num)]
    accum_list=[0]
    for i in range(0,num):
        accum_list.append(accum_list[-1]+files[i])
    for diagonal in range(1,num):
        for i in range(0,num-diagonal):
            j=i+diagonal  
            dp[i][j]=inf
            for k in range(i,j):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+accum_list[j+1]-accum_list[i])
                
    print(dp[0][-1])  
if __name__ == "__main__":
    testcases=int(input())
    for _ in range(testcases):
        num=int(input())
        files=list(map(int,input().split()))
        solution()