[프로그래머스 Level 3] 최적의 행렬 곱셈 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/12942

프로그래머스

 

 

점화식은 dp[i][j] = dp[i][m]+dp[m+1][j]+i*m*j와 같다. 이때 m은 for문으로 i부터 j값이 되도록 설정해주면 된다. 즉, m은 i~j를 나눠줄 위치이다. 이로 인해 가장 최적의 행렬 곱셈의 값을 구할 수 있다.

재귀를 이용해 문제를 풀었다. 주의할 점으로는 한 번 계산했던 i~j 범위가 또 계산이 되는 중복 현상이 발생하기 때문에 메모이제이션 기법을 사용했다.

 

#include <vector>

using namespace std;

vector<vector<int>> matrix;

int store[200][200];

int rec(int s, int e){
    
    if(store[s][e]!=0){
        return store[s][e];
    }
    
    if(e-s==0)
        return 0;
    
    if(e-s==1){
        return matrix[s][0]*matrix[s][1]*matrix[e][1];
    }
    
    int minNum = 987654321;
    
    for(int i = s ; i<e; i++){
        minNum = min(minNum, rec(s,i)+rec(i+1,e)+matrix[s][0]*matrix[i][1]*matrix[e][1]);
    }
    store[s][e]=minNum;
    
    return minNum;
}

int solution(vector<vector<int>> matrix_sizes) {
    int answer = 0;
    matrix = matrix_sizes;
    int maxNum = -1;
    answer = rec(0, (int)matrix_sizes.size()-1);
    return answer;
}