백준 11049 행렬 곱셈 순서

행렬의 곱셈 순서에 따라서 필요한 곱셈의 수가 달라진다. 최소 곱셈 횟수를 찾는 것이 문제의 목표이다.

어떤 n이 주어졌을 때, A₀A₁...A_n-1에서 모든 곱셈의 경우를 보고 그 최소값을 찾아야된다.

곱셈의 결과를 저장하는 배열을 dp라고하고 dp[i][j]를 i부터 j번째까지의 최소 곱셈의 수를 저장한다.
행렬의 행과 열의 값을 페어로 저장하여, a에 저장한다. a[i].first는 A_i행렬의 행, a[i].second는 A_i행렬의 열의 값을 가진다.

이때 dp[i][i] = 0이고,

1 <= k < n 인 k와 0 <= j < k 인 j에 대해서 아래와 같은 식이 만족된다.

 dp[i][i + k] = min(dp[i][i + j] + dp[i + j + 1][i + k] + a[i].first * a[i + j + 1].first * a[i + k].second,                                  dp[i][i + k])

i부터 i + k까지의 행렬을 i부터 i +j 와 i+j+1부터 i+k까지의 행렬로 나누어 곱셈의 값을 계산한 후에 그 최소값을 구하면 된다.

아래는 나의 풀이이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<long long, long long>> a;

int n;
long long dp[505][505];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        long long l, r;
        cin >> l >> r;
        a.push_back(make_pair(l, r));
        dp[i][i] = 0;
    }
    for (int k = 1; k < n; k++)
    {
        for (int i = 0; i + k < n; i++)
        {
            dp[i][i + k] = INT64_MAX;
            for (int j = 0; j < k; j++)
            {
                dp[i][i + k] = min(dp[i][i + k - 1 - j] + dp[i + k - j][i + k] + a[i].first * a[i + k - j].first * a[i + k].second,
                                   dp[i][i + k]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;

    return 0;
}