백준 11049 행렬 곱셈 순서 (C++)

11049번: 행렬 곱셈 순서

dp를 활용한 분할 정복 문제이다. 이 문제의 핵심은 점화식을 잘 세우는 것이다. 먼저 행렬의 곱 방식을 보자. 행렬 A (2,3), 행렬 B (3,4)가 있다고 할 때, 둘의 곱은 (2,4)가 되고 곱샘 횟수는 2 X 3 X 4가 된다. 즉 곱샘 횟수는 (A의 행 X A의 열 X B의 열)이 된다. cache[start][end]는 start번째 배열부터 end번째 배열까지의 최소 곱샘 횟수가 되고, 이는 cache[start][i] 와 cache[i+1][end]로 나눌 수 있다. 둘 사이의 곱샘 횟수인 v[start].first * v[i].second * v[end].second도 필요하다. 즉 점화식은 최종적으로 이렇게 나오게 된다.

cache[start][end] = cache[start][i] + cache[i+1][end] + v[start].first v[i].second v[end].second

dp내에서 반복문을 돌며 cache에 최솟값들을 저장하게되고, 최종적으로 cache[0,N-1)에 답이 저장되게 된다.
개인적으로 난이도가 있었던 문제였다. 지난 문제인 파일합치기와 유사한 문제였기에 비슷한 방식을 활용할 수 있었다.

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

#define INF pow(2,31) - 1

using namespace std;

int N;
vector<pair<int, int>> v;
int cache[500][500];

int dp(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++) {
        ret = min(ret, dp(start, i) + dp(i + 1, end) + v[start].first * v[i].second * v[end].second);
    }

    return ret;
}

void solution() {
    memset(cache, -1, sizeof(cache));

    cout << dp(0, N - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({ a,b });
    }

    solution();

    return 0;
}