행렬 곱셈 순서 (feat. 백준, 11049번)

행렬 곱셈 순서
https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

반응형

 

#include<iostream>
#include<cmath>
using namespace std;
int matrix[501][2], dp[501][501];
int main()
{
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	for (register int i = 1, r, c; i <= N; ++i)
		cin >> r >> c, matrix[i][0] = r, matrix[i][1] = c;
	for (register int i = 1, j, k; i < N; i++)
		for (j = 1; i + j <= N; j++) {
			dp[j][i + j] = static_cast<int>(1e9);
			for (k = j; k <= i + j; k++)
				dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i + j][1]);
		}
	cout << dp[1][N];
	return 0;
}
// *&)*@*