[BOJ] Q11049 행렬 곱셈 순서

[BOJ] Q11049 행렬 곱셈 순서

Question

Language: Python

Difficulty: Gold 3

A1=5X3 A2=3X2 A3=2X6 으로 이루어진 행렬이 있다고 했을때,

A1,A2,A3 행렬에 대해서 행렬 곱 연산을 구하는 과정은 ((A1,A2),A3) ==> 5X3X2 + 5X2X6 = 90 (A1,(A2,A3)) ==> 3X2X6 + 5X3X6 = 126 와 같이 총 2가지 경우가 존재한다. 아래의 경우로 행렬 연산을 수행했을 때, 최소 곱 연산으로 구할 수 있다.

A1,A2,A3,A4가 있을 때는 어떻게 될까? (A1),(A2,A3,A4) = A1-A1의 행렬곱(0) + A2-A4 행렬곱+ A1 row * A1[col] * A4[col] (A1,A2),(A3,A4) = A1-A2의 행렬곱 + A3-A4 행렬곱+ A1 row * A2[col] * A4[col] (A1,A2,A3),(A4) = A1-A3의 행렬곱 + A4-A4 행렬곱(0)+ A1 row * A3[col] * A4[col]

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

이처럼 행렬 연산 순서에 따라 행렬 곱의 연산 회수는 달라지기 때문에 비교를 해야된다.

A₁A₂A₃…A_n이 있을 때, 해당 행렬 곱의 최소 연산 아래와 같이 구할 수 있다.

A₁A_n=min((A₁A_k) + (A_k+1A_n) for 1<=i<=n)와 같은 점화식을 통해 각각의 최저 연산 횟수를 구할 수 있다.

이것을 이차원 배열로 생각해보면 쉽다

위의 예제를 예시로 들어보자

	A1	A2	A3
A1	0	A1A2	–
A2	–	0	A2A3
A3	–	–	0

맨 마지막에 들어가는 칸은 A₁A₃ 으로 (A₁A₂)A₃ , A₁(A₂A₃) 을 비교를 통해서 구한다. 행/열 차이가 1인 행렬들 부터 비교해가면서 A₁A_n=min((A₁A_k) + (A_k+1A_n) 해당 연산 결과들을 비교한다.

Solution

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