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

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

11049번: 행렬 곱셈 순서

 

cache에 cache[start][end] = "start행렬부터 end행렬까지 곱셈 연산 횟수의 최솟값"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

int n;
vector<pair<int, int>> matrix;
int cache[505][505];

void pre() {
	for (int i = 0; i < 505; i++) {
		for (int j = 0; j < 505; j++) {
			cache[i][j] = -1;
		}
	}
}

//start행렬부터 end행렬까지 곱셈 연산 횟수의 최솟값
int solve(int start, int end) {

	//행렬 하나일때
	if (start == end) {
		return 0;
	}

	int& ret = cache[start][end];

	if (ret != -1) {
		return ret;
	}

	ret = numeric_limits<int>::max();

	//mid를 정해서, (start~mid까지 곱셈 연산 횟수의 최솟값 => 연산결과:행렬A) + (mid+1~end까지 곱셈 연산 횟수의 최솟값 => 연산결과:행렬B) + (행렬A와 행렬B의 연산 횟수) 구한다
	for (int mid = start; mid <= end - 1; mid++) {
		ret = min(ret, solve(start, mid) + solve(mid + 1, end) + (matrix[start].first * matrix[mid].second * matrix[end].second));
	}

	return ret;
}

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

	pre();

	cin >> n;

	for (int i = 0; i < n; i++) {
		int r, c;
		cin >> r >> c;

		matrix.push_back(make_pair(r, c));
	}

	cout << solve(0, n - 1);

	return 0;
}