BOJ 11049 - 행렬 곱셈 순서 (dp)

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

파일 합치기와 매우 유사함

 

<문제설명>

최대 500개의 행렬 정보가 n*m 형태로 입력될 때, 이들은 순서대로 곱할 수 있음이 보장된다.

모든 행렬을 곱할 때 곱셈 연산의 최소횟수를 구하는 문제.

 

<풀이>

f(i, j) : i~j번째 행렬을 곱할 때 곱셈 연산의 최소 횟수

f(i, j) = f(i,k) + f(k+1,j) + a[i].f * a[k+1].f * a[j].s  ( i <= k < j ) 중 최소값을 구하면 된다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MAX = 5e2 + 5;
const int IMP = (1<<31)-1;
ll n, dp[MAX][MAX];
P a[MAX];

ll f(int i, int j) {
	if (i == j) return 0;
	
	ll& ret = dp[i][j];
	if (ret != -1) return ret;

	ret = IMP;
	for (int k = i; k < j; k++)
		ret = min(ret, (f(i, k) + f(k + 1, j)) + a[i].first * a[k+1].first * a[j].second);

	return ret;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].first >> a[i].second;

	memset(dp, -1, sizeof(dp));
	cout << f(0, n - 1) << '\n';
}