[PS] 백준 11049번 행렬 곱셈 순서

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

이전에 풀이했던 파일 합치기 문제와 유사하다. 해당 글의 링크는 아래에.

https://velog.io/@rhqjatn2398/PS-%EB%B0%B1%EC%A4%80-11066%EB%B2%88-%ED%8C%8C%EC%9D%BC-%ED%95%A9%EC%B9%98%EA%B8%B0

행렬 곱은 결합 법칙은 성립, 교환 법칙은 성립하지 않는다. 따라서 바로 옆에 있는 행렬끼리 곱셈 연산이 가능하다. 다시말해, 연속된 두 행렬 간 곱셈만이 가능하다.

브루트포스로 가능한지 살펴보는 것으로 시작하자.

n개의 행렬에 대해 생각해보면, 아래와 같다. 하나의 문제가 두개의 더 작은 문제로 구성되어 있는 것을 알 수 있다(재귀 피보나치와 유사). 재귀를 통해서 브루트포스로 접근하면 O(2^n) 일 것으로 보인다. 따라서 불가능하다.

(1번째) (곱셈) (2번째 부터 n번째 까지의 곱셈의 결과)
(1번째 부터 2번째 까지의 곱셈의 결과) (곱셈) (3번째 부터 n번째 까지의 곱셈의 결과)
...
...
...
(1번째 부터 n-1번째 까지의 곱셈의 결과) (곱셈) (n번째)

주목해야 할 부분은 동일한 문제는 항상 정답이 같다는 점과 동일한 문제를 여러번 풀어야 한다는 점이다.

그렇다면 작은 문제들을 memo 해놓고, 큰 문제를 구하는데 사용할 수 있다. 다이나믹 프로그래밍이다. 그렇다면 이제 점화식을 구해야하는데, 바로 위의 식에서 이미 그 형태가 나와있는 것을 알 수 있다.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int matrixes[500][2], dp[500][500];

void go() {
	fill_n(dp[0], 500 * 500, INT32_MAX);
	for (int i = 0; i < n; i++) {
		dp[i][i] = 0;
	}

	for (int len = 1; len <= n; len++) {
		for (int left = 0; left + len < n; left++) {
			int right = left + len;

			for (int curIdx = left; curIdx < right; curIdx++) {
				dp[left][right] = min(dp[left][right], matrixes[left][0] * matrixes[curIdx][1] * matrixes[right][1] + dp[left][curIdx] + dp[curIdx + 1][right]);
			}
		}
	}

	cout << dp[0][n - 1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> matrixes[i][0] >> matrixes[i][1];
	}

	go();

	
	return 0;
}