[백준 2024/10/01] 11049번 행렬 곱셈 순서

1. 문제

https://www.acmicpc.net/problem/11049

 

2. 접근 방법

https://www.youtube.com/watch?v=Tdl6VP4bS90

 

이 문제는 행렬의 계산 횟수를 구하는 문제이다. 위 영상이 이해에 큰 도움을 주었다.

그림으로 설명하기 위해 아래 그려 보았다.

(ABC)(DEFGH) 로 묶었다고 가정하였을 때, 계산 횟수는 z * c* h 가 된다. 즉, 이를 list를 이용해서 표현해 보면, 

row[x] * column[k] * column[y] 이다. 이후, 재귀적으로 ABC에 대해서, 그리고 (DEFGH)에 대해서 탐색해야 하므로

이를 다시 dfs에 범위를 재설정하여 넣어준다.

 

탈출 조건은 x와 y가 같은 값을 지닐 때, 이다.

또한 memoization을 사용해 주어야 하는데, dictionary를 사용하면 시간초과가 나기 때문에, 2중 배열을 이용해 주어야 한다.

 

3. 코드

import sys


def get_min_val(x, y, row, column):
    if y-x <= 0:
        return 0

    if dp[x][y] != -1:
        return dp[x][y]

    min_val = sys.maxsize

    for k in range(x, y):
        min_val = min(min_val, row[x]*column[k]*column[y] + get_min_val(x, k, row, column) + get_min_val(k+1, y, row, column))

    dp[x][y] = min_val
    return dp[x][y]


if __name__ == "__main__":
    n = int(input())
    r = []
    c = []
    for _ in range(n):
        row, column = map(int, input().split())
        r.append(row)
        c.append(column)
    dp = [[-1 for _ in range(n)] for _ in range(n)]
    print(get_min_val(0, n-1, r, c))