dp를 활용한 분할 정복 문제이다. 이 문제의 핵심은 점화식을 잘 세우는 것이다. 먼저 행렬의 곱 방식을 보자. 행렬 A (2,3), 행렬 B (3,4)가 있다고 할 때, 둘의 곱은 (2,4)가 되고 곱샘 횟수는 2 X 3 X 4가 된다. 즉 곱샘 횟수는 (A의 행 X A의 열 X B의 열)이 된다. cache[start][end]
는 start번째 배열부터 end번째 배열까지의 최소 곱샘 횟수가 되고, 이는 cache[start][i]
와 cache[i+1][end]
로 나눌 수 있다. 둘 사이의 곱샘 횟수인 v[start].first * v[i].second * v[end].second
도 필요하다. 즉 점화식은 최종적으로 이렇게 나오게 된다.
cache[start][end] = cache[start][i] + cache[i+1][end] + v[start].first v[i].second v[end].second
dp
내에서 반복문을 돌며 cache
에 최솟값들을 저장하게되고, 최종적으로 cache[0,N-1)
에 답이 저장되게 된다.
개인적으로 난이도가 있었던 문제였다. 지난 문제인 파일합치기와 유사한 문제였기에 비슷한 방식을 활용할 수 있었다.
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#define INF pow(2,31) - 1
using namespace std;
int N;
vector<pair<int, int>> v;
int cache[500][500];
int dp(int start, int end) {
if (start == end) return 0;
int& ret = cache[start][end];
if (ret != -1) return ret;
ret = INF;
for (int i = start; i < end; i++) {
ret = min(ret, dp(start, i) + dp(i + 1, end) + v[start].first * v[i].second * v[end].second);
}
return ret;
}
void solution() {
memset(cache, -1, sizeof(cache));
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++) {
int a, b;
cin >> a >> b;
v.push_back({ a,b });
}
solution();
return 0;
}