백준 #11049 행렬 곱셈 순서

백준 #11049 행렬 곱셈 순서

DP를 활용하는 문제.
이전까지 DP를 쓰는 문제는 top-down 방식을 썼는데(구현이 쉬워서) 실행 속도에 차이가 큼을 알고 나서는 bottom-up 방식을 쓰려고 한다.

dp[i][j]
= i부터 j까지의 최소 행렬 곱셈 개수
= min(dp[i][k] + dp[k + 1][j] + i번째 행렬의 세로 * k번째 행렬의 가로 * j번째 행렬의 가로)

• k의 범위: [i, j)

#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>

using namespace std;

int N;
vector<pair<int, int>> matrices;
int dp[500][500];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int i = 0; i < N; i++) {
        int r, c;
        cin >> r >> c;
        matrices.push_back({r, c});
    }
    for(int i = 0; i < N - 1; i++) {
        dp[i][i + 1] = matrices[i].first * matrices[i].second * matrices[i + 1].second;
    }
    for(int d = 2; d < N; d++) {
        for(int i = 0; i < N - d; i++) {
            int j = i + d;
            dp[i][j] = 1e9;
            for(int mid = i; mid < j; mid++) {
                dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + matrices[i].first * matrices[mid].second * matrices[j].second);
            }
        }
    }
    cout << dp[0][N - 1];
    return 0;
}