백준 11049 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

 

1차 시도는 브루트 포스였다. 매 번 가능한 모든 곱셈 결과 중 가장 작은 것을 합쳤다. 그럴싸하지만 이게 전체의 최적값을 보장하는 지 증명하지 못했고 --> 틀렸습니다 를 받았다. ㅠㅠ

 

2차 시도도 비슷했다. 원소 중에 가장 큰 값을 골라서 그 주변의 행렬을 곱했다. 이것역시 전체의 최적 값을 보장하지 않는다. --> 틀렸습니다 를 받았다.

 

결국 답은 Recursive + Memoization이었다. 즉 DP 문제였다... 

 

/* 행렬 곱셈 순서 */

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 500 + 1
#define IMAX 2100000000 // IMAX 보고싶다

using namespace std;

void input();
void solve();

long long int N, ANS;
pair<int, int> matrix[MAX];
int dp[MAX][MAX];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		matrix[i].first = a;
		matrix[i].second = b;
	}
}

int recur(int x, int y) {
	if (x == y) return 0;

	int& ret = dp[x][y];
	if (ret != 0) return ret;

	ret = INT_MAX;
	for (int i = x; i < y; i++) {
		ret = min(ret, recur(x, i) + recur(i + 1, y) + matrix[x].first * matrix[i].second * matrix[y].second);
	}
	return ret;
}

void solve() {
	cout << recur(0, N - 1) << '\n';
}