백준 11049 - 행렬 곱셈 순서, C++, DP

11049번: 행렬 곱셈 순서

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, r, c, res = 0;
pair<int, int> matrix[501];
int dp[501][501];   // left ~ right : 최소 연산 횟수

int MultiplyMatrix(int left, int right){
    if(left == right)
        return 0;
    
    int minimum = 999999999;

    if(dp[left][right] != -1)
        return dp[left][right];

    for(int i = left; i < right; i++){
        minimum = min(minimum, MultiplyMatrix(left, i) + MultiplyMatrix(i+1, right)
                    + (matrix[left].first * matrix[i].second * matrix[right].second));
    }
    dp[left][right] = minimum;
    return minimum;
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // input
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> matrix[i].first >> matrix[i].second;
    }

    // init
    memset(dp, -1, sizeof(dp));

    // solve
    cout << MultiplyMatrix(0, n-1) << '\n';
}

---

  또다시 학교 알고리즘 수업에 배운 내용들이다. solved.ac에서 클래스 기준으로 찾다가 비슷한 문제를 찾아 풀이를 했는데 아마 대부분 비슷하게 풀지 않을까 싶다.

 

- 처음 left, right 범위를 정합니다.

- dp 배열의 경우 left~right까지 했을 때 곱셈 연산의 최솟값을 담을 생각입니다.

- 함수의 for문에서는 중간점 i를 잡아 양쪽에서의 최솟값을 구하게 됩니다.