행렬 곱셈 순서

문제 링크

발상

파일 합치기 문제와 너무 똑같다. 구조적으로 완전히 같은 문제라고 생각해도 무방하다. 재귀적으로 구간을 양분하고 두 구간을 만드는데 사용된 비용 + 두 구간을 합치는 비용의 최솟값을 골라 갱신해나가면 된다. 이전 문제 설명에도 적어놓았듯, 구간을 합치는 비용과 구간을 만드는 비용 2가지만 잘 구분하면 된다.

점화식

$$\{\begin{array}{l}{n}_{s,e}=\text{s, e 구간을 하나로 합치는 최소 비용}\\ r_i=\text{i번째 행렬 행 크기}\\ c_i=\text{i번째 행렬 열 크기}\end{array}$$ $$n_{s,e}=\underset{k=s\to e-1}{\min }(n_{s,k}+n_{k+1,e}+r_i\times c_k\times c_j)$$

코드 ( Top-Down )

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct rc {
    int r, c;
};
int n;
vector<rc> arr;
vector<vector<int>> dp;
int r(int s, int e) {
    if (dp[s][e] != -1) return dp[s][e];
    int mn = 21e8;
    for (int i = s; i < e; i++) {
        int s1 = s == i ? 0 : r(s, i); // 왼쪽 구간 최적값 
        int s2 = i + 1 == e ? 0 : r(i + 1, e); // 오른쪽 구간 최적값
        int sp = arr[s].r * arr[i].c * arr[e].c + s1 + s2; // 최종 비용
        mn = sp < mn ? sp : mn; // 최소 비용 갱신
    }
    return dp[s][e] = mn;
}
int main() {    
    cin >> n; arr = vector<rc>(n + 1); dp = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].r >> arr[i].c;        
    }
    cout << r(1, n) << "\n";   
    return 0;
}

코드 ( Bottom-Up )

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct rc {
    int r, c;
};
inline int time(rc a, rc b) {
    return a.r * a.c * b.c;
}
int main() {    
    int n; cin >> n; vector<rc> arr(n + 1); vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].r >> arr[i].c;
    }
    for (int k = 1; k < n; k++) {        
        for (int i = 1; i <= n - k; i++) {
            int j = i + k;
            int mn = 21e8;
            for (int p = i; p < j; p++) {
                int s1 = dp[i][p];
                int s2 = dp[p + 1][j];
                int s = arr[i].r * arr[p].c * arr[j].c + s1 + s2;
                mn = s < mn ? s : mn;
            }
            dp[i][j] = mn;
        }
    }
    cout << dp[1][n];
    return 0;
}