[BOJ] 11049 : 행렬 곱셈 순서 - travelbeeee

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

---

[ 알고리즘풀이 ]

2차원 DP 배열을 이용해 문제를 해결해야합니다.

'DP[x][y] = x번 째 행렬부터 y번 째 행렬까지 곱했을 때 최소 연산의 수' 로 정의하겠습니다.

그러면 다음과 같은 점화식이 성립합니다.

 

for K = i+1~j-1,

      DP[i][j] = min(D[i][K] +D[K][j] + matrix[i]의 row * matrix[K]의 row * matrix[j]의 col)

 

따라서, 다음과 같은 순서로 DP 배열을 채워나갈 수 있습니다.

DP배열	1번 행렬	2번 행렬	3번 행렬	4번 행렬
1번 행렬	0	네번째	다섯번째	여섯번째
2번 행렬	0	0	두번째	세번째
3번 행렬	0	0	0	첫번째
4번 행렬	0	0	0	0

 

#include<iostream>
#include<vector>
#include<algorithm>
#define INT_MAX 2147483647
using namespace std;

int dp[505][505] = {};
vector<pair<int, int>> list;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, x, y;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		list.push_back(make_pair(x, y));
	}

	for (int i = N - 1; i >= 0; i--) {
		for (int j = i + 1; j < N; j++) {
			dp[i][j] = INT_MAX;
			for (int k = i; k <= j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + list[i].first * list[k].second * list[j].second);
			}
		}
	}
	cout << dp[0][N - 1];
}

---