BOJ 11049. 행렬 곱셈 순서

랭크 : 골드3

문제 풀이

DP 문제로 행렬을 곱할 때, 이전에 앞에 계산한 행렬을 덩어리로 생각하여, 뒤에서부터 앞으로 점점 곱하는 형태를 취하되, 이에 가능한 모든 계산을 dp로 수행합니다.
풀이법은 찾았는데, 계속 오류가 나서 풀이법이 잘못 되었는 지 찾는 도중에 찾은 것으로 https://cocoon1787.tistory.com/318에 자세한 설명이 적혀있습니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

struct Matrix {
    int a;
    int b;
    int value;
    Matrix() : a(0), b(0), value(0) {};
    Matrix(int a, int b, int value) : a(a), b(b), value(value) {};
    Matrix operator*(const Matrix& ref) { return {a, ref.b, a * b * ref.b + value + ref.value}; };
};

Matrix board[501][501];
int N, num1, num2;
int main() {
    fastio;
    cin >> N;

    for (int i=0; i < N; i++) {
        cin >> board[i][i].a >> board[i][i].b;
        for (int j=i-1; j >= 0; --j) {
            for (int k=i-1; k >= j; --k) {
                // cout << i << " " << j << " " << k << " " << board[k][j].a * board[k][j].b * board[i][k + 1].b + board[i][k + 1].value << endl;
                if (board[i][j].value == 0 || board[i][j].value > board[k][j].a * board[k][j].b * board[i][k + 1].b + board[k][j].value + board[i][k + 1].value)
                    board[i][j] = board[k][j] * board[i][k + 1];
            }
        }
    }

    // for (int i=0; i < N; i++) {
    //     for (int j=0; j <= i; ++j) {
    //         cout << board[i][j].value << " ";
    //     }
    //     cout << endl;
    // }
    cout << board[N-1][0].value << endl;
}

`알고리즘`	`시간복잡도`	`공간복잡도`
DP	$O(N ^ 3)$	$O(N ^ 2)$