[백준(BOJ)] 11049번 : 행렬 곱셈 순서 C++ 풀이(DP)

접근:

DP(Dynamic Programming)을 이용해서 푸는 문제.

발상은 행렬 곱셈이 이루어진 후에 두 행렬이 하나의 행렬로 이루어지기 때문에 작은 문제를 뭉쳐서 큰 문제를 해결 할 수 있음을 암시한다.

 

전략:

전체 행렬의 곱을 큰 문제로 보았을 때, 두 행렬의 곱으로 나눌 수 있고(구간 단위로),

이는 작은 문제로 나누어서 해결한다는 뜻이다.

그 행렬을 구할 수 있는 모든 경우의 수 중에 가장 연산이 가장 작으려면,  구간을 어떻게 나누었을 때 가장 곱 연산이 작은 지를 알면된다. 따라서 구간을 잘게 쪼개어 DP적으로 해결한다. 

맨 아래(기본 행렬 곱)에 도달 했을 때, 두 행렬의 곱 연산 수를 구하여서 그 값을 저장한다.

이를 쌓아서 올리면 전체 곱셈 순서를 구할 수 있게 된다.

 

-> 행렬을 나누는 경우의 수를 모두 확인할 때,

DP로 구해낸 이전 결과 값을 이용하여 전 행렬의 연산 수를 구하고, 그 둘의 행렬을 곱할 때의 수를 더한다.

이 값을 확인할 때 모두 확인하고 가장 작은 것을 취해서 dp 배열에 저장한다.

 

코드:

#include <iostream>
#include <vector>
#define INF INT32_MAX
using namespace std;
int n;
vector<pair<int,int>> matrix;
int dp[501][501];

int make(){
    for(int dis = 1; dis < n; dis++){ //행렬의 간격
        for(int i = 0 ; i < n - dis;i++){ //행렬 시작 위치
            dp[i][i+dis] = INF;
            for(int j=i; j <= i + dis ;j++){ //연산 최소값 중간 탐색
                dp[i][i+dis] = min(dp[i][i+dis], dp[i][j] + dp[j+1][i+dis] + matrix[i].first *matrix[j].second *matrix[i+dis].second);
            }
            
        }
    }

    return dp[0][n-1];
}

int main(){
    cin >> n;
    int a,b;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        matrix.push_back({a,b});
    }
    cout <<  make() << '\n';

    return 0;
}