[백준] 11049 - 행렬 곱셈 순서

행렬 곱셈 순서

생각 흐름

1. 이전에 풀었던 11066 - 파일 합치기 문제와 비슷하다.
2. 다만 최소값을 구하는 방식이 조금 다를 뿐이다.
3. dp값이 필요없는 것은 붙어있는 행렬 둘을 곱하는 것이다. 즉 이 문제도 범위를 1부터 늘려가며 풀면 된다.
4. 파일 합치기 문제와 같이 범위를 넓혀가며 풀면 될 것 같다.
5. 왼쪽과 오른쪽의 행렬을 곱할 때 발생하는 추가 비용은 어떻게 구할까?
6. 행렬의 모양이 어떻게 될지 dp에 그대로 저장한다.
7. 어차피 곱할 때의 모양은 왼쪽은 (시작행 기준열)이고 오른쪽은 (기준+1행 끝열) 이 될 것이고 이때 곱하는 비용은 시작행 기준열 끝열일 것이다. (기준열과 기준+1행은 같은 값)

풀이

구간에서 왼쪽과 오른쪽 행렬을 곱할 때 추가되는 비용은 arr[j][0] * arr[k][1] * arr[j+i][1]이 될 것이다.
이 값과 왼쪽(dp[j][k])과 오른쪽(dp[k+1][j+i])의 비용을 모두 더하면 된다.

코드

import sys
import math


scan = sys.stdin.readline


def solution():
    N = int(scan())
    arr = [list(map(int, scan().split())) for _ in range(N)]

    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(1, N):
        for j in range(N - i):
            dp[j][j + i] = math.inf
            for k in range(j, j + i):
                dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k+1][j + i] + arr[j][0] * arr[k][1] * arr[j + i][1])

    sys.stdout.write("%d" % dp[0][N-1])


solution()