[C++] BAEKJOON 11049 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

동적계획법 중 top-down 방식을 사용했습니다.

dp[i][j] 는 i 부터 j 까지의 행렬을 곱하는 연산의 최솟값 으로 정의하였습니다.

i, j 가 인접해있다면, 즉 1 차이가 난다면 두 행렬의 곱셈을 직접 계산해주고 인접해있지 않다면 부분으로 쪼개 각각을 계산해준 후, 계산한 결과인 두 개의 행렬의 곱셈은 직접 계산해주었습니다.

#include <iostream>
#include <cstring>

using namespace std;

int matrix[500][2];
int dp[501][501];

int go(int i,int j){
    if (dp[i][j] != -1) return dp[i][j];
    if (i==j) return 0;
    if (i+1 == j){
        return matrix[i][0]*matrix[i][1]*matrix[j][1];
    }
    
    for (int k=i;k<j;k++){
        int temp = go(i,k) + go(k+1,j);
        int matrixMul = matrix[i][0]*matrix[k][1]*matrix[j][1];
        
        if (dp[i][j] == -1 || dp[i][j] > temp+matrixMul)
            dp[i][j] = temp+matrixMul;
    }
    return dp[i][j];
}

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N;
    
    memset(dp,-1,sizeof(dp));
    
    for (int i=0;i<N;i++){
        cin >> matrix[i][0];
        cin >> matrix[i][1];
    }
    
    cout << go(0,N-1) << "\n";
    return 0;
}