[ 백준 11049번 ] 행렬 곱셈 순서 파이썬

[백준 11049번 바로가기]

11049번: 행렬 곱셈 순서

손글씨로 설명을 대체합니다

논리

주어진 여러 행렬의 곱을 두 행렬의 곱으로 간주합니다

점화식

점화식입니다

동작 순서 예시

코드의 동작 순서를 숫자로 나타내 보았습니다

코드

import sys

def minimum_matrix_operation():

    # inputs
    N = int(sys.stdin.readline())
    matrices = [None] * N
    for i in range(N):
        matrices[i] = list(map(int, sys.stdin.readline().split()))

    # table[i][j]: i-th-Matrix * ... * j-th-Matrix 의 최소 연산 횟수
    table = [[0] * N for _ in range(N)]

    for j in range(1, N):
        for i in range(j-1, -1, -1):
            candidate = sys.maxsize
            for k in range(i, j):
                candidate = min(candidate 
                                , matrices[i][0] * matrices[k][1] * matrices[j][1]
                                + table[i][k] + table[k+1][j])
            table[i][j] = candidate

    print(table[0][N-1])
    return

minimum_matrix_operation()