[boj] 백준 11049 행렬 곱셈 순서 (c++) - dp

[문제]

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

11049번: 행렬 곱셈 순서

 

[풀이]

dp[i][j] = i~j 구간 행렬의 곱셈 연산 최솟값을 저장.

1~n 까지의 행렬을 연산하기 위한 많은 경우의 수가 존재하므로, k를 기점으로 (1~k 까지의 연산 최솟값) + (k+1~n 까지의 연산 최솟값) + (1, k) (k+1, n) 행렬의 곱셈 연산 값을 구해 더해줌으로써 최솟값을 구할 수 있다.

 

(m x n) 행렬과 (n x k) 행렬이 곱해지면 곱셈 연산 값은 (m x n x k)가 되고 이 행렬은 (m x k) 행렬이 된다.

따라서 (1, k) (k+1, n) 행렬의 곱셈 연산 값은 (1번 행렬의 r값 x k번 행렬의 c값(=k+1번 행렬의 r값) x n번 행렬의 c값)으로 계산 가능하다. 

 

코드를 보면 3중 for문을 돌고 있는데 첫번째 for 문은 구간 범위의 크기, 두번째 for문은 구간의 시작점, 세번째 for문은 구간의 중간 기준점을 나타낸다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n;
int dp[501][501];
pair<int, int> matrix[501];

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

    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> matrix[i].first >> matrix[i].second;
    }

    for(int i=1; i<=n; i++){ //구간 범위 크기
        for(int j=1; i+j<=n; j++){ //시작 지점
            dp[j][i+j] = INF;
            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].first * matrix[k].second * matrix[i+j].second);
            }
        }
    }

    cout << dp[1][n];

}