[프로그래머스/C++] 최적의 행렬 곱셈

 

 

문제

문제 설명

 

풀이

 

 

처음에 행렬이 곱할 수 있는 순서대로 주어지는건지 고민했지만, 순서대로 계산이 가능하도록 주어질 것이라고 보고 문제를 풀었다.

 

문제를 보면 최악의 경우 200개의 행렬의 모든 순서를 전부 계산해보고 풀기에는 무리가 있어서 DP로 풀기로 했다.

​

A번째에서 C번째 행렬까지의 곱셈연산을 구한다고 하면 (A행렬과 C행렬 사이에 B행렬이 있다고 가정)

 

[A 행렬 ~ B 행렬의 최소 곱셈연산 횟수] + [B 행렬 ~ C 행렬의 최소 곱셈 연산횟수] + [이번 연산 횟수] 값이 최소가 되는 행렬을 찾으면 A 행렬 ~ C 행렬의 최소 곱셈 연산 횟수가 된다.

 

즉, 이전에 계산한 최소 곱셈연산 횟수가 다음 계산에도 사용되므로 DP로 풀 수 있다.

​​

[아이디어 정리]

 

1. 2차원 DP를 만들고 DP[st][ed]에는 st번째 행렬부터 ed행렬까지의 연산횟수의 최소값을 저장한다.
2. DP를 활용해 구하고 싶은 행렬의 최소 연산횟수를 구한다.
3. 모든 행렬을 계산한 결과값인 DP[0][ed]의 값을 return하면 된다. (ed는 matrix의 마지막 index)

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> DP;
vector<vector<int>> realMatrix;
void CalcDP(int st, int ed)
{
    int minV=200*200*200*200;
    int nowV;
    for (int i=st; i<ed; i++)
    {
        nowV=DP[st][i]+DP[i+1][ed]+realMatrix[st][0]*realMatrix[i][1]*realMatrix[ed][1];
        if (minV>nowV)
        {
            minV=nowV;
        }
    }
    DP[st][ed]=minV;
}

int solution(vector<vector<int>> matrix_sizes) {
    int answer = 0;
    DP=vector<vector<int>>(matrix_sizes.size(),vector<int>(matrix_sizes.size(),0));
    realMatrix=matrix_sizes;
    //size가 2면 차수는 1
    for (int i=1; i<matrix_sizes.size(); i++)
    {
        for (int st=0; st+i<matrix_sizes.size(); st++)
        {
            CalcDP(st, st+i);
        }
    }
    return DP[0][matrix_sizes.size()-1];
}

 

---

 

이런 DP는 코딩테스트에 나오면 정말 고마울 것 같다

단, 범위는 잘 설정해야 할 듯

 

프로그래머스