[백준] 11049번 행렬 곱셈 순서

11049번: 행렬 곱셈 순서

ABCD를 계산하는 방법은

A(BCD), (AB)(CD), (ABC)D

세 가지로 나눌 수 있고

이 중에서의 최솟값이 ABCD의 값이 된다.

 

A(BCD)에서 BCD는

B(CD), (BC)D

두 가지로 나눌 수 있고

이 중에서의 최솟값이 BCD의 값이 된다.

 

(AB)(CD), (ABC)D도 분해하여 구한 최솟값을 저장하면

ABCD의 최솟값을 구할 수 있다.

 

이 과정을 표로 나타내 보면

 

ABCD를 구하기 위해선

A와 BCD, AB와 CD, ABC와 D를 구해야 한다.

 

BCD를 구하기 위해선

B와 CD, BC와 D,

ABC를 구하기 위해선

A와 BC, AB와 C

를 구해야 한다.

 

즉, 최종 값인 빨강을 구하기 위해선

노랑 이하의 값들이 필요하고

노랑을 구하기 위해선

초록 이하의 값들이 필요하다.

 

이걸 점화식으로 나타내면

arr[i][j] = min(arr[i][j], arr[i][k] + arr[k+1][j] + a*b*c)

이 된다.

 

여기서 i와 j는 식의 처음과 끝이고

k는 식을 나누는 부분이다.

ex) (AB)(CDE)에서 i=0, k=1, j=4

 

a*b*c는 최종적으로 남은 두 가지 무리를 곱하는 순서이다.

ex)

(AB) = 3X4

(CDE) = 4X6

a*b*c = 3*4*6

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int N, a, b, Min = INT_MAX;
class info {
public:
	int a, b, val;
	info() {}
	info(int a, int b, int val) {
		this->a = a, this->b = b, this->val = val;
	}
}arr[501][501];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		arr[i][i] = info(a, b, 0);
		if (i != 0) arr[i - 1][i] = info(arr[i - 1][i - 1].a, arr[i][i].b, arr[i - 1][i - 1].a * arr[i - 1][i - 1].b * arr[i][i].b);
	}
	for (int t = 2; t < N; t++) {
		for (int i = 0, j = i + t; j < N; i++, j++) {
			arr[i][j].val = INT_MAX, arr[i][j].a = arr[i][i].a, arr[i][j].b = arr[j][j].b;
			for (int k = i; k < j; k++) arr[i][j].val = min(arr[i][j].val, arr[i][k].val + arr[k + 1][j].val + arr[i][j].a*arr[i][k].b*arr[i][j].b);
		}
	}
	cout << arr[0][N - 1].val;
	return 0;
}