백준 11049번 : 행렬 곱셈 순서

Algorithm/problem

백준 11049번 : 행렬 곱셈 순서 - dp

DingCoDing 2022. 11. 28. 20:12

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같

www.acmicpc.net

#include <iostream>
#include <climits>

using namespace std;

int N;
int d[503];
int matrix[503][2];
long long dp[503][503];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> matrix[i][0] >> matrix[i][1];
        d[i] = matrix[i][1];
    }

    d[0] = matrix[1][0];
    for (int diagonal = 1; diagonal <= N - 1; diagonal++) {
        for (int i = 1; i <= N - diagonal; i++) {
            int j = i + diagonal;
            dp[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d[i - 1] * d[j] * d[k]);
            }
        }
    }

    cout << dp[1][N] << '\n';
    return 0;
}