[C++] 백준 11049번 - 행렬 곱셈 순서

이차원 배열을 사용해야하는 dp문제

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, a, b;
int minMul[501][501];
vector<int> v;

int matOrder(vector<int>& v, int n) {
    for (int i = 1; i < n; i++)
        minMul[i][i] = 0;

    for (int length = 2; length <= n; length++) {
        for (int i = 1; i < n - length + 1; i++) {
            int j = i + length - 1;
            minMul[i][j] = INT_MAX; 
            for (int k = i; k <= j - 1; k++) {
                int q = minMul[i][k] + minMul[k + 1][j] + v[i - 1] * v[k] * v[j];
                if (q < minMul[i][j])
                    minMul[i][j] = q;
            }
        }
    }
    return minMul[1][n - 1];
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (i == n - 1) {
            v.push_back(a);
            v.push_back(b);
        }
        else {
            v.push_back(a);
        }
    }

    cout << matOrder(v, n + 1) << endl;
    return 0;
}