[백준] 11049번 행렬 곱셈 순서 C++ 문제풀이

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

11049번: 행렬 곱셈 순서

 

문제 풀이

맨 처음에는 완전탐색하는 방향으로 문제를 해결할까 고민했는데, 아무리 생각해도 아니여서 고민을 했다.

DP로 문제를 어떻게 해결할까 고민하다가, 다른 블로거 분의 풀이를 보고 이해했다.

일단 A, B, C, D가 있다고 가정하게 된다면

AB, BC, CD를 계산한 후 ABC행렬의 계산은 A(BC), (AB)C를 비교하는 식으로 확장해 나가면 되는 문제였다.

DP[i][j] 는 i번째 행렬부터 j번째 행렬까지 곱셈 연산의 최소값을 의미한다.

소스 코드

#include <iostream>
using namespace std;

int n;
int matrix[501][2];
int dp[501][501] = { 0 };


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

    for (int i = 1; i < n; i++) {
        for (int j = 1; i + j <= n; j++) {
            dp[j][i + j] = 2147483647;
            for (int k = j; k <= i + j; k++) {
                dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i + j][1]);
            }
        }
    }

    cout << dp[1][n];

    return 0;
}