백준 11049번: 행렬 곱셈 순서 (Python, PyPy3)

접근

이전에 풀었던 DP 문제와 유사하게 풀었다. 하지만 Knuth's Optimization은 적용하지 못해 PyPy3으로만 풀 수 있었다.

2021.04.07 - [코딩/백준 (Python)] - 백준 11066번: 파일 합치기 (Python, PyPy3)

백준 11066번: 파일 합치기 (Python, PyPy3)

dp[i][j]에 i번째부터 j번째까지의 행렬을 곱한 최소 결과를 저장하면 dp[0][n]의 값(첫 행렬부터 마지막까지 행렬까지 곱한 결과의 최소값)은
dp[0][0] + dp[1][n] + A * (BC...N) 곱하는 비용
dp[0][1] + dp[2][n] + (AB) * (C...N) 곱하는 비용
...
dp[0][n - 2] + dp[n - 1][n] + (AB...N-2) * (N-1.N) 곱하는 비용
dp[0][n - 1] + dp[n][n] + (AB...N-1) * N 곱하는 비용
값 중 최소값일 것이다.

코드

import sys

n = int(sys.stdin.readline())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().split())))
dp = [[[0, 0, 0] for _ in range(n)] for __ in range(n)]
knuth = [[0 for _ in range(n)] for __ in range(n)]
for i in range(n):
    dp[i][i] = matrix[i] + [0]
for x in range(1, n):
    for i in range(n - x):
        j = i + x
        dp[i][j][2] = 2 ** 31
        dp[i][j] = [matrix[i][0], matrix[j][1], dp[i][j][2]]
        for k in range(i, j):
            dp[i][j][2] = min(dp[i][j][2], dp[i][k][2] + dp[k + 1][j][2] + dp[i][k][0] * dp[i][k][1] * dp[k + 1][j][1])
print(dp[0][n - 1][2])

더 생각해 볼 것?

아직 스스로가 Knuth's Optimization 적용 조건을 제대로 이해하지 못한 것 같다. 왜 Knuth's Optimization 적용이 안되는지 다시 검토해볼 필요가 있다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!