백준 11049번 행렬 곱셈 순서

문제 링크입니다: https://www.acmicpc.net/problem/11049

left~right까지 행렬을 곱했을 경우 최소 연산 횟수가 cache[left][right]에 저장되고 이를 2개의 부분문제로 바꾸는 것이 핵심이였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 500;

const int INF = 987654321;

 

int N;

pair<int, int> matrix[MAX];

int cache[MAX][MAX];

 

//left~right까지 연산하는데 드는 비용

int minCalc(int left, int right)

{

        if (left == right)

               return 0;

 

        int &result = cache[left][right];

        if (result != -1)

               return result;

 

        result = INF;

        for (int i = left; i < right; i++)

               //두 부분으로 나눈다

               result = min(result, minCalc(left, i) + minCalc(i + 1, right) + matrix[left].first*matrix[i].second*matrix[right].second);

 

        return result;

}

 

int main(void)

{

        cin >> N;

        for (int i = 0; i < N; i++)

               cin >> matrix[i].first >> matrix[i].second;

 

        memset(cache, -1, sizeof(cache));

        cout << minCalc(0, N - 1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~