백준 11049 행렬 곱셈 순서

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

 

서론

DP와 분할정복 아이디어를 이미 갖고 있었음에도 구현을 못한 문제

행렬을 어떻게 곱해서 재귀함수의 리턴으로 넘겨줘야할지를 해결하지 못했다.

다른분의 풀이를 참고하여 구현한 지금에서도 왠지모를 석연찮음이 남아있다.

 

---

아이디어

11066번 문제와 유사하다.

전체적인 풀이 아이디어는 이 문제와 같다.

https://hydroponicglass.tistory.com/4

 

위 문제와 다른점은 행렬을 계산하는 것.

(AB)(CD)에서 ABCD는 AB와 CD의 곱이다. 따라서 왼쪽분할인 AB의 결과값과 오른쪽분할인 CD의 결과값에 AB와 CD를 곱한 결과값을 더해줘야한다.

즉 재귀함수의 리턴값은 왼쪽+오른쪽+(왼쪽*오른쪽)

 

리턴값의 왼쪽*오른쪽은

행렬이 (3*2)*(2*4)*(4*5) = (3*5)와 같이 계속 곱해주면 처음과 끝이 살아남는 구조라서

(AB)(CD)에서

AB = {A.a, B.b}, CD = {C.a, D.b},

(AB)(CD) =  A.a*B.b(=C.a)*D.b

(AB)(CD)에서 start는 A, end는 D, mid는 B다.

 

---

구현

//c++

#include <iostream>
#include <algorithm>
#include <cstring>

typedef struct {
	int a, b;
}s;

int dp[501][501];
s input[501];

int rec(int start, int end) {
	//std::cout << start << end << std::endl;
	if (start == end) return 0;
	if (dp[start][end] != 0x3f3f3f3f) return dp[start][end];

	for (int mid = start; mid < end; mid++) {
		int left = rec(start, mid);
		int right = rec(mid+1, end);
		dp[start][end] = std::min(left + right + input[start].a * input[mid].b * input[end].b, dp[start][end]);
		//std::cout << dp[start][end] << std::endl;
	}

	return dp[start][end];

}

int main() {
	memset(dp, 0x3f, sizeof(dp));
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> input[i].a >> input[i].b;
	}
	rec(0, n-1);
	std::cout << dp[0][n-1];

}