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

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

11049번: 행렬 곱셈 순서

행렬 곱셈 순서에 따라 연산량이 적어지는데 잘 생각해보면 (a b) (b c) 차원인 두 행렬을 곱할 때 a * b * c 의 연산횟수가 필요하다. 즉 가운데 b가 큰 순서대로 먼저 곱하는것이 횟수를 줄일 수 있다. 하지만 당장 b가 큰것을 줄이는 순서가 최종적으로 최적의 방법이 아닐 수 있기 때문에 구간 s~e 에서 모든 연산을 수행해봐야 한다.

DP[s][e]를 s 번째 행렬과 e 번째 행렬 구간을 곱할 때 필요한 최소 연산 횟수로 정의하면

DP[s][e] = argmin(dp[s][i] + dp[i+1][e] + (s의 행)*(i의 열 or i+1의 행)*(e의 열)) 이 됩니다.

그러면 메모이제이션을 사용한 재귀방식으로 구현하여 해결할 수 있습니다.

#include <iostream>
#include <limits.h>
#include <memory.h>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

int n;
pair<int, int> p[501];
int dp[501][501];
int recv(int s, int e) {
	if (s == e) {
		return 0;
	}
	int& ret = dp[s][e]; 
	if (~ret) return ret;
	ret = INT_MAX;
	for (int i = s; i < e; i++) {
		ret = min(ret, recv(s, i) + recv(i + 1, e) + p[s].first * p[i].second * p[e].second);
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	memset(dp, -1, sizeof(dp));
	cout << recv(0, n - 1);
}