(c++) 동적계획법 BOJ 11049번: 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

 

 

---

 

 

 

문제 개요

 

 

재귀를 이용한 메모이제이션을 사용하는 동적 계획법 문제이다.

 

나름대로 점화식을 만들어보면

 

$$  M[i][j] = min(M[i][j], M[i][k]+M[k+1][j]+D(i,k,j)) $$

 

문제의 예제로 주어진

(5, 3), (3, 2), (2, 6)들의 최솟값을 구하려면

각 경우가 1번째, 2번째, 3번째라고 했을 때

1 * (2 * 3), (1 * 2) * 3 이렇게 두 가지 경우의 수가 존재한다.

 

모든 경우를 구한다고 생각해보았을 때

 

M[1][3] 

 

M[1][1] + M[2][3](M[2][2] + M[3][3] + D) + D

M[1][2](M[1][1] + M[2][2] + D) + M[3][3] + D

 

※ D는 M 사이의 행렬의 곱셈, M[i][i]은 행렬 자기 자신

 

for (int i = start; i <= end; i++) {
        ret = min(ret, mult(start, i) + mult(i+1, end) + mult_result(start, i+1, end));
}

 

행렬의 곱은 아래의 코드처럼

시작 행렬의 첫 번째 X 중간 행렬의 첫 번째 X 끝 행렬의 두 번째

이렇게 하면 행렬의 여러 개의 곱도 나타낼 수 있다.

int mult_result(int start, int i, int end) {
    return matrix[start].first * matrix[i].first * matrix[end].second;
}

 

 

 

코드

 

 

 

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int> > matrix(500);
int min_mt[250];
int cache[500][500];
int mult_result(int start, int i, int end) {
    return matrix[start].first * matrix[i].first * matrix[end].second;
}
int mult(int start, int end) {
    if (start == end) return 0;
    int& ret = cache[start][end];
    if (ret != -1) return ret;
    ret = 1e9;
    for (int i = start; i <= end; i++) {
        ret = min(ret, mult(start, i) + mult(i+1, end) + mult_result(start, i+1, end));
    }
    return ret;
}

int main(void) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> matrix[i].first >> matrix[i].second;
    }
    fill(&cache[0][0], &cache[499][500], -1);
    cout << mult(0, n-1);
}