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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 최적의 행렬 곱셈

최적의 행렬 곱셈

문제

크기가 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이하의 자연수 입니다.
• 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

 

풀이

입출력 예시

 

풀이

이 문제는 연쇄 행렬 곱셈이라는 알고리즘을 알고 있어야 풀 수 있는 문제였다.

 

[알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication)

[알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication)

 

해당 알고리즘을 알고 있었다면 조금 쉽게 풀렸겠지만, 나는 그렇지 않았기에.. 이번에 새로 공부했다. 다이나믹 프로그래밍 문제들은 하나같이 다 어려운 것 같다..

 

#include <string>
#include <vector>

using namespace std;

long long dp[201][201];
long long d[201];

int solution(vector<vector<int>> matrix_sizes) {
    int answer = 0;
    int m_size = matrix_sizes.size();
    
    d[0] = matrix_sizes[0][0];
    for (int i = 0; i < m_size; i++) {
        d[i + 1] = matrix_sizes[i][1];
    }
    
    for (int n = 0; n < m_size; n++) {
        for (int i = 1; i <= m_size - n; i++) {
            int j = i + n;
            
            if (i == j) {
                dp[i][j] = 0;
            }
            else {
                dp[i][j] = 9999999999999999;
                for (int k = i; k <= j - 1; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j]);
                }
            }
        }
    }
    
    answer = dp[1][m_size];
    
    return answer;
}