[백준 C++] 11049번: 행렬 곱셈 순서

1. 문제

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

11049번: 행렬 곱셈 순서

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스 코드

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;

pair<int, int> matrix[501];
int dp[501][501];

int main()
{
	// N : 행렬의 갯수 입력
	int N, r, c, A, B, C;
	cin >> N;

	// 행렬 입력
	for (int i = 1; i <= N; i++)
	{
		cin >> r >> c;
		matrix[i] = { r, c };
	}

	// DP 풀이
	// A X B 행렬 * B X C 행렬 = A X B X C
	// dp[A][C] = A ~ C까지 최소 연산 수
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; i + j <= N; j++)
		{
			A = j;
			C = j + i;
			dp[A][C] = INF;	// DP 초기화

			for (int k = j; k <= C; k++)
			{
				B = k;
				dp[A][C] = min(dp[A][C], dp[A][B] + dp[B + 1][C] + matrix[A].first * matrix[B].second * matrix[C].second);
			}
		}
	}

	cout << dp[1][N];

	return 0;
}