[백준 11049] 행렬 곱셈 순서

문제 링크 => 11049번: 행렬 곱셈 순서 (acmicpc.net)

11049번: 행렬 곱셈 순서

---

다이나믹 프로그래밍 문제이다.

 

많은 분들이 푼 문제이다 보니 꽤 유명한 문제인 것 같다.

 

이 문제는 행렬의 곱셈 연산 횟수의 최솟값을 찾는 문제이다.

 

이 문제를 base case와 그렇지 않은 경우를 함수 dp(int start, int end) 를 통해 먼저 살펴보도록 한다.

(ABC 행렬이 있다고 가정할 때 start = 0, end = 2 를 의미함)

 

일단 memoziation 을 활용하기 위한 2차원 배열 memo[501][501] 을 설정하도록 하였다.

 

1. start == end ) 곱셈 연산의 횟수는 0 이다. (ex : 임의의 행렬 A 에 대하여 곱셈 과정이 없음)

 

2. start + 1 == end ) 곱셈 연산의 횟수는 v[start].first * v[end].first * v[end].second 이다. (ex : 임의의 행렬 곱 AB 에 대하여 곱셈 과정은 row(A) * row(B) * col(B) 로 값을 나타냄)

 

3. 그 외의 경우 ) 함수 dp(start, end) 가 start ~ end 사이에서의 Minimum 값을 리턴한다는 목표로 두었기 때문에 다음과 같은 식이 형성된다.

for (int i = start; i < end; i++) {
		int result = dp(start, i) + dp(i + 1, end) + v[start].first * v[i].second * v[end].second;
		if (!memo[start][end] || result < memo[start][end]) memo[start][end] = result;
}

(dp(start , i) + dp(i+1, end)) + (v[start].first * v[i].second * v[end].second) 의 의미를 다음의 예시를 통해 알아보도록 한다.

 

ex ) 행렬 ABCDEF 의 곱셈 연산의 최솟값을 구하려고 한다.

 

dp(start, 2) + dp(3, 5) => 행렬 ABC 의 곱셈 연산의 최솟값 + 행렬 DEF 의 곱셈 연산의 최솟값을 의미함

v[start].first * v[i].second * v[end].second => 행렬 ABC와 DEF 의 마지막 곱셈 연산의 횟수를 더해줘야 한다. 즉, row(A) * col(C) * col(F) = row(A) * row(D) * col(F) 의 값으로 2가지 표현이 가능하다. (v[start].first * v[i+1].first * v[end].second 으로 대체해도 가능하다는 소리)

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#define endl '\n'
using namespace std;
typedef long long ll;

int memo[501][501], n;
vector<pair<int, int>> v;

int dp(int start, int end) {
	if (start == end) return 0;
	if (memo[start][end]) return memo[start][end];
	if (start + 1 == end) {
		return memo[start][end] = v[start].first * v[end].first * v[end].second;
	}
	for (int i = start; i < end; i++) {
		int result = dp(start, i) + dp(i + 1, end) + v[start].first * v[i+1].first * v[end].second;
		if (!memo[start][end] || result < memo[start][end]) memo[start][end] = result;
	}
	return memo[start][end];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
	}

	cout << dp(0, v.size() - 1);

	return 0;
}