baekjoon 11409:행렬 곱셈 순서

baekjoon 11409 행렬 곱셈 순서

11409번 행렬 곱셈 순서

접근

dp를 한다는 것은 결국 다 해본다는 뜻이다.
ac25683번 처럼 단조감소가 있으면 그리디로 풀리겠지만
그렇게 단조감소부분을 제거하고 나면 결국은 dp이다.
모든 경우를 단순히 다 해보는 방법은 순열로 각 곱하기를 줄세우는 것이니 500!의 시간복잡도가 걸린다.
무조건 터진다.
그래서 마지막에 계산하는 곱하기를 기준으로 dp를 짰다. 이렇게 하니 각 dp마다 최대 500이 걸리고
그런 dp가 \(\binom{500}{2}\)개 정도 있다는 결론이 나와서 \(\frac{500^{3}}{2} = 1\)억 좀 안되게 나와서 할만하다고 생각했다.

코드

//11049
#include <iostream>
#include <vector>
#include <array>
#include <limits.h>
using namespace std;
array<array<int, 500>, 500> cache;
int dp(int i, int j, vector<pair<int, int>>& v);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<pair<int, int>> v(n);
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  for(auto& i:cache){
    fill(i.begin(), i.end(), -1);
  }
  cout << dp(0, n-1, v);
  return 0;
}
int dp(int i, int j, vector<pair<int, int>>& v){
  if(i == j) return 0;
  int& ret = cache[i][j];
  if(ret != -1) return ret;
  ret = INT_MAX;
  for(int k = i; k < j; k++){
    ret = min(ret, dp(i, k, v) + dp(k+1, j, v) + v[i].first*v[k].second*v[j].second);
  }
  return ret;
}

배운 점

dp를 쓰면서 전체 status를 계속 보관하고 있어야 할 것 같은 것을 변형시켜 일부를 기준으로 부분문제를 정의하는 방법을 배운 것 같다.