백준 11049 행렬 곱셈 순서 혼내주기

 

종만북으로 한창 공부할 때 힘들게 풀었었는데, 다시 풀어도 마냥 쉽지는 않은 문제.
dp를 이용해 중복 계산이 없도록 하면서 모든 순서대로 계산한 결과의 최솟값을 재귀적으로 찾으면 된다.

11066 파일 합치기 문제와 아주 유사하다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;


int arr[500][2], cache[500][500];
int n;

void input() {
    fastio;
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> arr[i][0] >> arr[i][1];
}

int min(int a, int b) {return a > b ? b : a;}
int dfs(int from, int to) {
	if(from == to) return 0;

	int& ret = cache[from][to];
	if(ret != -1) return ret;

	ret = 2e9;
	for(int i = from; i < to; ++i) {
		ret = min(ret, dfs(from, i) + dfs(i+1, to) + arr[from][0]*arr[i][1]*arr[to][1]);
	}
	return ret;
}

int main() {
    input();
	memset(cache, -1, sizeof(cache));
	cout << dfs(0, n-1);
}