BOJ 11049 행렬 곱셈 순서

 

문제 링크 : https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

결합 순서에 따라 비용이 달라지는 유명(?)한 문제이다.

 

 

위의 예를 들여다 보면 

 

dp[a][b] = min(dp[a][b],
                        dp[a][i] + dp[i+1][b] + (a 행렬의 행) * (i 행렬의 열= i+1 행렬의 행) * (b 행렬의 열) );

 

을 얻을 수 있다. 

전체 코드는 아래와 같다.

 

#include<bits/stdc++.h>

using namespace std;

vector<int> arr[501];
int dp[501][501];

int recur(int a, int b){
    if(a==b) return 0;
    int &ret=dp[a][b];
    if(ret!=-1) return ret;
    
    ret=INT_MAX;
    for(int i=a;i<b;i++)
        ret=min(ret,
                recur(a,i)+recur(i+1,b)+arr[a][0]*arr[i][1]*arr[b][1]);
    
    return ret;
}

int main(){
    memset(dp,-1,sizeof dp);
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b; scanf("%d%d",&a,&b);
        arr[i].push_back(a), arr[i].push_back(b);
    }
    
    printf("%d\n", recur(1,n));
}

 

dp 초기값을 -1 로 하는 것은 memset 을 이용하는 게 편하기 때문인데,

사실 지금 문제라면 큰 값을 초기값으로 하는 것이 논리적으로는 더 합당할 것이다.