행렬 곱셈 순서

• 유명한 DP 문제인 행렬 연쇄 곱셈 문제이다.
• n<500이라는 제한 조건은 옵티멀한 O(nlogn)풀이 대신에 O(n^3)으로도 통과되도록 의도한 것 같지만, Python으로 시간 안에 통과하려면 마이크로 최적화가 필요하다. 자세한 것은 행렬 연쇄 곱셈 참조.
• 동일한 구현을, 좀더 가독성있게 작성한 코드는 최적의 연쇄 행렬을 참고. 동일한 문제지만 n<200 이어서 쉽게 통과된다.

"""Solution code for "BOJ 11049. 행렬 곱셈 순서".

- Problem link: https://www.acmicpc.net/problem/11049
- Solution link: http://www.teferi.net/ps/problems/boj/11049
"""

import sys


def main():
    n = int(sys.stdin.readline())
    r_and_c = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]

    sizes = [r for r, _ in r_and_c]
    sizes.append(r_and_c[-1][1])
    dp = [[0] * n for _ in range(n)]
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            sz_ij = sizes[i] * sizes[j + 1]
            m = min(min_ik + min_kj + sz_ij * sz_k for min_ik, min_kj, sz_k in
                    zip(dp[i][i:j], dp[j][i + 1:j + 1], sizes[i + 1:j + 1]))
            dp[i][j] = dp[j][i] = m

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


if __name__ == '__main__':
    main()