[C++] 백준 11049: 행렬 곱셈 순서 (동적계획법)

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

소요 시간: 58분

해결: O

 

풀이 설계하는데 시간이 조금 걸렸습니다.

풀고 보니 직관적인 문제인데 ps 조금 쉬었더니 바로 둔해지네요...

---

문제 분할

일련의 행렬들의 곱이 주어졌을 때, 어디서부터 어떤 순서로 곱해야 가장 적게 계산할까요?

... 잘 모르겠습니다.

 

반대로 그 행렬들을 모두 곱한 결과가 있을 때, 마지막에 어느 부분에서 곱셈이 발생했을까요?

마지막 결과 또한 부분 행렬 A와 B를 곱한 결과일테니, 그 경계가 되는 행렬을 찾으면 문제를 분할할 수 있습니다.

 

i번째 행렬이 그 경계라면 아래처럼 식을 정리할 수 있습니다.

캐싱

start~end까지 행렬을 곱했을 때 연산횟수 중 최솟값을 저장합니다.

---

코드

const int INF = numeric_limits<int>::max();
const int SZ = 501;

typedef struct{
    int r, c;
} Mat;

int N;
vector<Mat> mats;

int cache[SZ][SZ];
int solve(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++){
        int op_cnt = solve(start, i) + solve(i+1, end);
        op_cnt += mats[start].r * mats[i].c * mats[end].c;
        
        ret = min(op_cnt, ret);
    }
    
    return ret;
}