[Algorithm] 11049: 행렬 곱셈 순서

📦11049: 행렬 곱셈 순서

---

[알고리즘 풀이] 강동규
Reviewed by midade midang (devmidade12@gmail.com)
Reviewed:: 2024-02-19
문제 확인하기

풀이

• 이 문제는 1시간을 고민해도 전혀 갈피를 잡지 못하겠어서 결국 https://cocoon1787.tistory.com/318의 풀이를 참고했다. 확실히 DP 문제에 약하다고 느껴진다.

• dp[n][m] 는 n 에서 m 까지의 범위를 행렬 연산했음을 의미한다.

• 3중 for 문을 사용하여 행렬 연산의 범위, 시작 지점, 범위 연산을 지정해 계산한다.

• i 는 행렬의 범위를 지정한다. i = 2 일 경우, dp[n][m] 에서 m-n, n과 m 사이의 거리, 차이가 2라는 뜻이다.

• j 는 행렬의 시작 지점을 말한다. j = 3, i = 2 인 경우 dp[3][5] 로 3에서 시작해서 5번째까지의 행렬을 구한다.

• mid 는 범위 안에서의 실질적인 연산을 진행한다. dp[3][10] 을 구한다고 하면 mid 는 3~10 의 값이고, 반복문을 돌면서 dp[3][3], dp[3][4], … 를 구한다.

• 최종적으로는 dp[1][N] 을 구하면 1~N 까지의 행렬 연산의 최솟값을 구할 수 있다.

• 혼자 생각할 때 dp로 느낌이 들기는 했지만 어떻게 풀어야 할지 감이 오지 않았다. 해당 문제를 풀이하는 방식이 이해를 하니까 끄덕일 수 있었지만 체득이 필요할 것 같다.

코드

#include <iostream>
 
#define endl '\n'
using namespace std;
 
int N;
int matInfo[501][2];
int dp[501][501];
 
void Input(){
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> matInfo[i][0] >> matInfo[i][1];
    }
}
 
void Solution(){
    for(int i=1; i<N; i++){
        for(int j=1; i+j<=N; j++){
            dp[j][i+j] = INT32_MAX;
            for(int mid=j; mid<=i+j; mid++){
				dp[j][i+j] = min(dp[j][i+j], dp[j][mid] + dp[mid+1][i+j]                         + matInfo[j][0]*matInfo[mid][1]*matInfo[i+j][1]);
            }
        }
    }
    cout << dp[1][N] << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}