백준] 11049 - 행렬 곱셈 순서

시간 제한 : 1초

메모리 제한 : 256MB

입력

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

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

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

출력

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

소스코드

#include <iostream>
#include <climits>
using namespace std;
int dp(int arr[], int size)
{
	int** table;
	int i, j, k, L, tmp, result;

	table = new int*[size + 1];
	for (int i = 0; i < size + 1; i++)
		table[i] = new int[size + 1];

	for (int i = 1; i <= size; i++)
		table[i][i] = 0;

	for (int i = 1; i <= size; i++)
	{
		for (int j = 1; j <= size - i; j++)
		{
			int k = i + j;
			table[j][k] = INT_MAX;
			for (int L = j; L <= k - 1; L++)
			{
				tmp = table[j][L] + table[L + 1][k] + arr[j - 1] * arr[L] * arr[k];
				if (tmp < table[j][k])
					table[j][k] = tmp;
			}
		}
	}

	result = table[1][size - 1];
	
	for (int i = 0; i < size + 1; i++)
		delete table[i];
	delete table;
	
	return result;
}
int main(void)
{
	int n, a, b;
	int arr[501];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		arr[i] = a;
	}
	arr[n] = b;
	cout<<dp(arr, n + 1);
}

Tip

행렬을 곱셈하는 순서에 따라서 연산 횟수가 달라진다는 문제로, 동적계획법(다이나믹)으로 풀면 되는 문제다. 2차원 테이블을 사용하기 때문에 다소 어렵게 느껴질 수 있다. 이 코드와 관련된 자세한 내용은 이전에 블로그에 게시해두었으니 참고하면 될 듯하다.

연속 행렬 곱셈 - http://twinparadox.tistory.com/183