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

0.  문제 링크

 

 

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

11049번: 행렬 곱셈 순서

---

1.  풀이 방법

 

 

• 예전 알고리즘 시간에 풀었던 문제라 비교적 간단하게 풀 수 있었음
• 2022.04.15 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 - 연쇄 행렬곱셈 (Chained Matrix Multiplication)
• 예전에 내가 쓴 글을 보면 자세히 설명해 놓았음
• 키 포인트는 i ~ i + dia까지의 최적을 구하기 위해서는 i ~ k, k +1 ~ i + dia에서 k를 조절해 가면서 최적 값을 구하면 되는 것임
• 결론적으로 DP로 해결하였음

---

2.  코드

 

 

import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    maps = [[]] * n
    dp = [[float('inf')] * n for _ in range(n)]     # 최솟값을 구하기 위해 최댓값을 미리 넣어놓음

    for i in range(n):
        maps[i] = list(map(int, input().split()))

    for i in range(n):
        dp[i][i] = 0        # 대각선은 0으로 처리해놓음

    for dia in range(1, n):
        for i in range(n - dia):
            for k in range(i, i + dia):
                # i ~ i + dia까지 최적은 i ~ k, k + 1 ~ dia 까지 계산하면 됨
                # 여기서 최솟값을 찾으면 해결할 수 있음
                temp = maps[i][0] * maps[k][1] * maps[i + dia][1]
                dp[i][i + dia] = min(dp[i][i + dia], dp[i][k] + dp[k + 1][i + dia] + temp)

    print(dp[0][n - 1])

---

3.  마무리