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

프로그래머스

여러 개의 행렬을 곱할 때, 곱하는 순서에 따라 연산 횟수가 달라집니다. 행렬 곱셈에서 최소한의 연산을 사용하여 곱하는 순서를 찾는 것이 이 문제의 목표입니다. 이를 위해 동적 계획법(Dynamic Programming)을 사용하여 각 부분 문제를 풀고, 그 결과를 저장해 전체 문제를 해결합니다.

 

크기가 [5 x 3], [3 x 10], [10 x 6]인 행렬이 있을 때, (1*2) * 3의 순서로 곱하게 되면

5 * 3 * 10 (150) + 5 * 10 * 6 (300) = 450회의 연산을 하게 되지만

1 * (2*3)의 순서로 곱하게 되면  (5 * 3 * 6) + (3 * 10 * 6) = 270회로 연산을 끝낼 수 있습니다.

 

풀이 방법

이 문제는 다이나믹 프로그래밍 문제입니다.

dp 배열을 정의 할 때에는 dp[i][j] = i ~ j까지의 최소 연산 수의 형태로 정의 하며, 점화식은 아래와 같습니다.

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]);

 

[i ~ k]까지 곱한 행렬을 A

[k+1 ~ j ]까지 곱한 행렬을 B 라고 할 때

i ~ j까지의 연산 수 = dp[i][k] + dp[k+1][j] + A와 B의 연산 수 vs 기존에 구한 i ~ j 까지의 연산 수

 

---

모든 행렬은 바로 옆의 행렬과만 곱할 수 있습니다.

최소 연산 수를 구하기 위해서는 결국 모든 연산을 전부 해봐야 하기 때문에

우선 2개의 행렬 부터 곱 연산 수를 기록해줍니다.

dp[0][1] = 0번 행렬 * 1번 행렬의 곱 연산 수;
dp[1][2] = 1번 행렬 * 2번 행렬의 곱 연산 수;

 

 

이후 행렬을 3개로 늘려서 기록을 이어갑니다.

// dp[0][2] = min((0 * 1) * 2 , 0 * (1 * 2));
dp[0][2] = dp[0][1] + dp[2][2] + matrix[0][0] * matrix[1][1] * matrix[2][1] vs 
	dp[0][0] + dp[1][2] + matrix[0][0] * matrix[0][1] * matrix[2][1]];

 

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> matrixs) {
    
    int MAX = 1000000000;
    int n = matrixs.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int length = 1; length < n; length++)
    {
        for (int i = 0; i + length < n; i++)
        {
            int j = i + length;
            dp[i][j] = MAX;
            
            for (int k = i; k < j; k++)
            {
                int cost = dp[i][k] + dp[k+1][j] + matrixs[i][0] * matrixs[k][1] * matrixs[j][1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n-1];
}