백준 11049번: 행렬 곱셈 순서

[문제 링크]

11049번: 행렬 곱셈 순서

---

먼저 N x M 행렬과 M x K 행렬을 곱하면 N x K 행렬이 만들어진다는 것을 알고있어야 한다.

 

행렬 A, B, C, D가 있을 때 만들 수 있는 곱셈 순서는 다음과 같다.

(A) * (BCD),

(AB) * (CD),

(ABC) * (D)

 

2개로 묶인 행렬은 바로 곱해주면 되지만 3개 이상으로 묶인 행렬은 그 최솟값을 구하기 위해 다시 곱셈 순서를 나눠줘야 한다.

 

예를 들어 (A) * (BCD) 에서 (BCD)를 (B) * (CD) 와 (BC) * (D) 두가지로 나눌 수 있다.

 

위 과정을 재귀적으로 반복하는 함수를 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int proc[501][2], memo[501][501];

int min(int a, int b) { return a < b ? a : b; }

int Topdown(int start, int end)
{
	if (start == end) return 0;
	if (start + 1 == end) return proc[start][0] * proc[start][1] * proc[end][1];

	int& ret = memo[start][end];
	if (ret != 0) return ret;

	ret = INF;

	for (int i = start; i < end; i++)
		ret = min(ret, Topdown(start, i) + Topdown(i + 1, end) + proc[start][0] * proc[i + 1][0] * proc[end][1]);

	return ret;
}

int Bottomup(int start, int end)
{
	for(int i = 1; i <= end; i++)
		for (int j = i - 1; j > 0; j--)
		{
			memo[j][i] = INF;

			for(int k=j; k<i; k++)
				memo[j][i] = min(memo[j][i], memo[j][k] + memo[k + 1][i] + proc[j][0] * proc[k + 1][0] * proc[i][1]);
		}

	return memo[start][end];
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> proc[i][0] >> proc[i][1];

	cout << Topdown(1, N) << endl;

	cout << Bottomup(1, N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 99 day