====== 최적의 행렬 곱셈 ======

===== 풀이 =====
  * 동적 계획법의 유명한 문제인 [[ps:구간 분할 방식에 관한 DP#연쇄 행렬 곱셈]]문제이다.
  * O(nlogn) 알고리즘이 최적으로 알려져 있지만, 여기에서는 교과서에서 알려주는 O(n^3) 알고리즘으로 풀었다. 
  * 추후에 O(nlogn) 알고리즘을 구현해보고 업데이트 예정.
  * BOJ의 [[ps:problems:boj:11049|행렬 곱셈 순서]]도 동일한 문제이지만, n<500 이라서 코드를 조금 더 최적화시켜야 통과 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "Programmers 12942. 최적의 행렬 곱셈".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12942
- Solution link: http://www.teferi.net/ps/problems/programmers/12942
"""


def solution(matrix_sizes):
    n = len(matrix_sizes)
    dp = [[0] * n for _ in range(n)]
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] +
                matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]
                for k in range(i, j))

    return dp[0][-1]
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_4}}