11049 행렬 곱셈 셈 순서

///*
#include <stdio.h>
 
int arr[505][3] = { 0 };
long long dp[505][505] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &arr[i][1], &arr[i][2]);
    }
 
    for (int d = 1; d < n; d++) {
        for (int i = 1; i + d <= n; i++) {
            long long minV = 1000000000000;
            for (int mid = i; mid + 1 <= i + d; mid++) {
                long long tmp = dp[i][mid] + dp[mid + 1][i + d] + arr[i][1] * arr[mid][2] * arr[i + d][2];
 
                if (minV > tmp)
                    minV = tmp;
            }
 
            dp[i][i + d] = minV;
        }
    }
    printf("%lld", dp[1][n]);
}