백준 11049 (C++) 행렬 곱셈 순서

연쇄 행렬 곱셈

일반적으로, i * j 행렬과 j * k 행렬을 곱하면 원소단위 곱셈의 실행 횟수는 다음과 같다.

i * j * k 번

 

 

 

실행 횟수가 행렬의 크기에 따라 결정된다. 따라서 최적의 순서도 행렬의 크기에만 의존한다.

 

 

n개의 행렬  \({A}_{1}\) ... \({A}_{n}\))을 곱하는 모든 순서의 가지 수를  \({T}_{n}\)이라고 하자.

A1을 마지막으로 곱하는 순서의 집합의 가지수는  \({T}_{n-1}\)이다. (A_1...A_n까지 곱하는 서로 다른 순서의 가지수)

An을 마지막으로 곱하는 순서의 가지 수 또한\({T}_{n-1}\)일 것이다.

따라서 다음과 같은 부등식이 나온다.

 

$$T_n >= T_{n-1} +T_{n-1} = 2 * T_{n-1}$$

 

 

두 개의 행렬을 곱하는 법은 하나이므로 T2= 1이다.

위의 식은 따라서

$$T_n >= 2^{n-2}$$

이다.

 

 출력 조건이

 

 

정답은 \({2}^{31-1}\) 보다 작거나 같은 자연수이다.
또한, 최악의 순서로 연산해도 연산 횟수가 $2^{31-1}$보다 작거나 같다.

인 이유이다.

 

 

1 <= k <= n인 모든 k에 대해  \({d}_{k}\)를  \({A}_{k}\)열의 수라고 하면, \({A}_{k}\)의 크기는 \({d}_{k-1}\) * \({d}_{k}\)이다.

다음과 같이 재귀 관계식을 구축할 수 있다.

 

M[i][j] = i<j일때 i번째 행렬~j번째 행렬까지 곱하는 원소단위 곱셈의 최소 횟수
M[i][i] = 0

 

 

구해야하는 답 = M[1][n]
M[1][n] = M[1][k] + M[k+1][n] + d0dkdn
M[i][j] = i<=k<=j-1일때 min(M[i][k] + M[k+1][j] + di-1dkdj)

 

 

 

 

 

 

 

728x90

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const int MAX = 501;
const int INF = 987654321;
int n, trash;
int M[MAX][MAX]; // M[i][j] = i<j일때 i번째 행렬~j번째 행렬까지 곱하는 원소단위 곱셈의 최소 횟수
int d[MAX];
// 답 = M[1][n]
// M[1][n] = M[1][k] + M[k+1][n] + d0dkdn
// M[i][j] = i<=k<=j-1일때 min(M[i][k] + M[k+1][j] + di-1dkdj)
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        cin >> d[i]; cin >> trash;
    }
    cin >> d[n-1] >> d[n];
   //for (int i = 0; i < n+1; i++) cout << d[i] << " ";

    for (int i = 1; i <= n; i++) {
        M[i][i] = 0;
    }
    for (int diagonal = 1; diagonal <= n-1; diagonal++) { // diagonal - 1은 주 대각선의 바로위에 있는 대각선
        for (int i = 1; i <= n - diagonal; i++) {
            int j = i + diagonal; // j - i = diagonal = 몇번째 대각선인지 나타냄
            M[i][j] = INF;
            for (int k = i; k <= j-1; k++) {
                M[i][j] = min(M[i][j], M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j]);
            }
        }
    }
    cout << M[1][n];
    return 0;
}

심화

이 알고리즘으로 최소 곱셈의 횟수뿐 아니라 그 순서도 알 수 있다.

P[i][j]라는 새로운 배열에 최소 값이 되는 k의 값을 저장하면 된다.

 

 

적을게 워낙 많아서 일단 올리고 고치는 걸로...