백준 11049번 행렬 곱셈 순서

백준 11049번 행렬 곱셈 순서

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n, diagonal;
//행렬A_i~부터 A_j까지 곱셈 연산 최소값 저장 M[i][j];
int M[501][501];
int d[501];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> d[i + 1];
    }
 
    for (diagonal = 1; diagonal <= n - 1; diagonal++) {
        for (int i = 1; i <= n - diagonal; i++) {
            int j = i + diagonal;
            for (int k = i; k <= j - 1; k++) {                
                if (M[i][j]==0||(M[i][j] > M[i][k] + M[k+1][j] + d[i - 1] * d[k] * d[j]) ) {
                    M[i][j] = M[i][k] + M[k+1][j] + d[i - 1] * d[k] * d[j];
                }
            }
        }
    }
    cout << M[1][n];
 
    return 0;
}

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

연쇄 행렬 곱셈 알고리즘을 이용해서 풀 수 있는 문제였습니다.

diagonal1	diagonal2	diagonal3	diagonal4	diagonal5
0	30	64	132	226	348
	0	24	72	156	268
		0	72	198	366
			0	168	392
				0	336
					0

위의 그림은 M[i][j]의 완성된 값을 의미하며

diagonal은 대각선을 의미하고 

Case1:diagonal1

M[1][2]==30,M[2][3]==24......

Case2:diagonal2

M[1][3]==64,M[2][4]==72..... 

이런 식으로 이해하면 됩니다. 

연쇄행렬곱셈의 점화식입니다.

이 방법은 시간 복잡도 O(n^3)이지만 O(n^2), O(nlgn) 방법도 있다고 하니 찾아봐야겠습니다. 

위 사진의 예제는 백준의 예제와 다른 입력을 사용해봤습니다.