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

문제 설명

크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.

행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.

각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.

제한사항

• 행렬의 개수는 3이상 200이하의 자연수입니다.
• 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
• 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

---

풀이

실패
점화식을 결국 알아내지 못해서 풀이를 찾아보았다. 행렬 연산과 관련하여 dp를 활용하는 문제를 최근 코딩테스트에서 접했었는데, 비슷한 문제를 또 틀리고 나니 오기가 생긴다. dp문제에 대한 접근이 너무 서투른 것 같다는 생각이 들어서, 아직 안 푼 문제 중 dp문제를 우선적으로 풀거나 릿코드에서 dp분류의 문제를 더 풀어봐야겠다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> matrix_sizes) {
    int dp[200][200] = {0,};
    vector<vector<int>> v = matrix_sizes;
    for(int size = 1; size < v.size(); ++size){
        for(int i = 0; i + size < v.size(); ++i){
            int j = i + size;
            
            int min_res = 2000000000;
            for(int k = i; k < j; ++k){
                min_res = min(min_res, dp[i][k] + dp[k+1][j] + v[i][0]*v[k][1]*v[j][1]);
            }
            dp[i][j] = min_res;
        }
    }
    
    return dp[0][v.size() - 1];
}