백준 11049번 행렬 곱셈 순서

백준 11049번: 행렬 곱셈 순서

아이디어

cache[시작 위치][끝나는 위치]에 최소 연산 횟수를 메모이제이션 한다. 최소 연산 횟수는 그림처럼 분할정복 느낌으로 구한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
pair<int, int> arr[500];
int cache[500][500];

int solve(int start, int end) {
    if (start == end) return 0;

    int& ret = cache[start][end];
    if (ret != -1) return ret;

    ret = INT_MAX;

    for (int i = start; i < end; i++) {
        ret = min(ret, solve(start, i) + solve(i+1, end) + arr[start].first*arr[i].second*arr[end].second);
    }
    return ret;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for (int i = 0; i < N; i++) {
        int r, c;
        cin >> r >> c;
        arr[i] = {r, c};
    }

    memset(cache, -1, sizeof(cache));
    cout << solve(0, N-1);
    return 0;
}

여담

엄청 쉬워보여서 풀기 시작했는데 결국 식을 잘못 세워서 맞왜틀?? 하고 한참 헤매다 찾아봤다.. 조그만 예제 만들고 식을 세우면서 풀면 괜찮을듯?