[백준 11049] 행렬 곱셈 순서 (C++)

먼저, brute-force나 백트래킹이 가능한지 확인해보자. $N$은 최대 $500$이므로, $\sum_{k = 0}^{498} \begin{pmatrix} 500 - k \\ 2 \end{pmatrix} = 20833250$가 된다. 대략 2천만 정도 되어 구현한다면, 통과는 될거 같긴하다...

근데, 구현이 복잡하니 일단 다른 풀이를 생각해보자. 정 안되면 구현해야지 ㅠㅠ

문제 상황 자체가 행렬 여러 개가 주어졌을 때, 곱셈 시 연산 횟수가 최소가 되어야 한다.

그런데, 한 번에 구하는 게 힘드니 문제를 분할해서 접근해보자.

$A_1A_2 \cdots A_{n-1}A_n$은 $(A_1A_2 \cdots A_k)(A_{k+1} \cdots A_{n-1}A_n)$으로 분할이 가능하다. 또, 연산 횟수가 최소인 k를 구하기 위해, $A_1A_2 \cdots A_k$과 $A_{k+1} \cdots A_{n-1}A_n$가 필요하다.

즉, 문제를 분할하고 이전 상태를 통해 다음 상태를 도출할 수 있으므로 DP로 풀 수 있다는 것이 된다.

d[i][j]는 i번째 행렬부터 j번째 행렬까지의 곱셈시 최소 연산 횟수를 저장한다.

i번째 행렬부터 j번째 행렬까지의 최소 연산 횟수를 한 번에 구하는 것은 어렵기 때문에, 위의 아이디어를 이용해 문제를 분할해서 접근해보자.

$i \le k \le j$를 만족하는 $k$에 대해 $(A_i \cdots A_k) (A_{k+1} \cdots A_j)$로 분할하면, d[i][j]는 $A_i \cdots A_k$의 연산 횟수와 $A_{k+1} \cdots A_j$의 연산 횟수의 합에 두 개의 연속된 행렬 곱 연산 결과를 곱할 때 필요한 연산 횟수가 더해져야 한다.

$A_i$가 m[i].X $\times$ m[i].Y 크기의 행렬이고 $A_k$가 m[k].X $\times$ m[k].Y 크기의 행렬이면, $A_i \cdots A_k$는 m[i].X $\times$ m[k].Y 크기의 행렬이 된다.

또, $A_{k+1} \cdots A_j$ 역시도 m[k+1].X $\times$ m[j].Y크기의 행렬이된다.

따라서, $(A_i \cdots A_k) (A_{k+1} \cdots A_j)$를 곱하는데 필요한 연산 횟수는 m[i].X * m[k].Y * m[j].Y가 됨을 알 수 있다.

따라서, d[i][j] = d[i][k] + d[k + 1][j] + m[i].X * m[k].Y * m[j].Y가 된다는 것을 알 수 있다.

하지만, $k$의 범위가 앞서 언급했듯 $i \le k \le j$이므로 해당 범위의 $k$값에 대한 연산 횟수들이 d[i][j]의 후보가 된다.

따라서, 그중 최소가 d[i][j]가 되도록 해야한다.

점화식을 구했으니 이를 바탕으로 구현하면 된다.
brute-force로 안풀어도 된다. 다행이다ㅠㅠ

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, r, c;
int d[501][501];
pair<int, int> m[501];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> m[i].X >> m[i].Y;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; i + j <= n; j++) {
			d[j][i + j] = INT_MAX;
			for (int k = j; k < i + j; k++) {
				d[j][i + j] = min(d[j][i + j],
								  d[j][k] + d[k + 1][i + j] + m[j].X * m[k].Y * m[i + j].Y);
			}
		}
	}

	cout << d[1][n];
}