cache[시작 위치][끝나는 위치]에 최소 연산 횟수를 메모이제이션 한다.
최소 연산 횟수는 그림처럼 분할정복 느낌으로 구한다.
#include <bits/stdc++.h>
using namespace std;
int N;
pair<int, int> arr[500];
int cache[500][500];
int solve(int start, int end) {
if (start == end) return 0;
int& ret = cache[start][end];
if (ret != -1) return ret;
ret = INT_MAX;
for (int i = start; i < end; i++) {
ret = min(ret, solve(start, i) + solve(i+1, end) + arr[start].first*arr[i].second*arr[end].second);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int r, c;
cin >> r >> c;
arr[i] = {r, c};
}
memset(cache, -1, sizeof(cache));
cout << solve(0, N-1);
return 0;
}
엄청 쉬워보여서 풀기 시작했는데 결국 식을 잘못 세워서 맞왜틀?? 하고 한참 헤매다 찾아봤다..
조그만 예제 만들고 식을 세우면서 풀면 괜찮을듯?