백준 11049번 행렬 곱셈 순서

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

 

기억할 점

행렬 범위 i는 대각선으로 내려가는 행렬곱을 구하기 위함이므로 N-dia까지의 범위에서 진행해야 한다.

M[i][j]는 min 비교 전에 큰 값으로 초기 설정해야한다.

정답의 범위를 확인해서 그에 맞게 지정한다. 

처음에 99999로 했더니 틀려서 9999999999999로 했더니 맞음.

 

#include<iostream>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm>
#include<queue>

using namespace std;


long long M[501][501];
int d[510];
int N;
vector<pair<int, int > > vec;


int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		vec.push_back({ a,b });
	}

	for (int i = 0; i < N; i++)
	{
		d[i] = vec[i].first;
	}
	d[N] = vec[vec.size() - 1].second;

	for (int dia = 0; dia < N; dia++)
	{
		for (int i = 1; i <= N - dia; i++)
		{
			int j = i + dia;
			if (i == j)
			{
				M[i][j] = 0;
				continue;
			}

			M[i][j] = 9999999999;
			for (int k = i; k < j; k++)
			{
				M[i][j] = min(M[i][j], M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]);
			}
		}
	}
	cout << M[1][N] << endl;
	

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}