BOJ 11049 행렬 곱셈 순서

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

 

그리디와 dp 를 두고 세시간 넘게 고민하다가 뇌가 안되는거 같아서 포기하고 풀이방향을 보고 풀었다. dp 는 어느정도 익숙해졌다 싶었는데, 이렇게 과감하게도 풀 수 있구나 싶어서 꼭 기억을 해두려고 한다. 너무 분해.

---

dp 라는 생각이 가장 직관적으로 다가왔는데, 점화식을 어떻게 잡아야 할지 감이 안왔다. 기본적으로

 

dp[start][end] = start 부터 end 까지 연산의 최소값

 

으로 메모이제이션을 하는 쉽게 알 수 있다.

 

그런데 여기서

dp[start][end] 와 dp[start][end + 1] 사이의 관계식(점화식)은 어떻게 만들까? 둘에 관계가 보이지 않았다.

start ~ end 에서 start ~ end + 1 한개만 늘어나도 완전히 산식이 달라지지 않나?

 

그런데 점화식이라는게 그렇게 간단하게만 세워지는게 아니었다. 여기서는 더 과감한 점화식이 필요함.

 

dp[start][end +1] = min(

                 dp[start][end] + dp[end+1][end+1] + (start ~ end 의 결과 행렬) * (end +1 행렬) 연산,

                 dp[start][end-1] + dp[start][end +1] + (start ~ end - 1 의 결과 행렬) * (end ~ end + 1 행렬) 연산,

                 ····

                 dp[start][start] + dp[start + 1][end + 1] +  (start 행렬) * (start + 1 ~ end + 1 행렬) 연산

  )

 

이렇게 모든 범위를 다 쪼개서 점화식을 세우면 된다...

 

정답 코드

#include<bits/stdc++.h>
using namespace std;

int n;
int dp[501][501];
vector<pair<int, int>> a;
int solve(int s, int e){
    if(~dp[s][e]) return dp[s][e];
    if(s == e) return 0;
    int ret = 987654321;
    for(int i=1;i<=e-s;i++){
        ret = min(ret, solve(s, e - i) + solve(e - i + 1, e) + a[s].first * a[e - i].second * a[e].second);
    }
    dp[s][e] = ret;
    return ret;
}

int main(){
    cin >> n;
    int k1, k2;
    for(int i=1;i<=n;i++){
        cin >> k1 >> k2;
        a.push_back({k1, k2});
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, n-1);
}