[Algorithm]Baekjoon 11049번 :: 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 
using namespace std;
 
int n;
int matrix[501][2] = { 0 };
int dp[501][501] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> matrix[i][0] >> matrix[i][1];
    }
    
    for (int i = 1; i < n; ++i) // 간격크기
    {
        for (int j = 1; j + i <= n; ++j) // 시작점
        {
            dp[j][j + i] = 0x3f3f3f3f;
            for (int k = j; k <= i+j; ++k)
            {
 
                dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[j + i][1]);
            }
        }
    }
 
    cout << dp[1][n];
}
 
 
 

 

3중 반복문을 통해 1~N까지를 세세하게 쪼개서 값을 업데이트 해나가는 방식이다.

dp[1][n]은 1번행렬부터 n번행렬까지를 곱했을때의 최솟값. 즉 answer인데, 이 1~n을 세세하게 쪼개서 전부 탐색해서 최솟값을 dp테이블에 업데이트 시키는것이다.

크기가 1인것부터 시작해서 n-1인것까지 업데이트시키는것이기 때문에 (크기가 1이라는것은 (1,2)  (2,3)인것처럼 시작행렬과 끝행렬의 차이가 1이라는 으미), 값을 다시 재활용할 수 있다.

예를들어 2~7의 최솟값을 먼저 구하는과정에서 3~5의 값을 먼저 계산해서 업데이트한다.

후에 3 ~ 8의 최솟값을 구하는과정에서 마찬가지로 3~5의 값을 사용할 때가 오는데, 이전에 2~7최솟값 구할 때 구해놨으니 재활용이 가능하다.

 

3 ~ 8까지를 구한다했을 때 실제 dp값 업데이트하는 코드를 살펴보면 과정중에서 j == 3, k ==5, i+j == 8 인 경우가 나온다.

 

그러면 dp[3][8] = min(dp[3][8], dp[3][5] + dp[6][8] + matrix[3][0] * matrix[5][1] * matrix[8][1]);

 

이렇게 될 것이다. 그냥 말 그대로 (3,5)구간의 최솟값 + (6,8)구간의 최솟값 + 3,5,8행렬의 곱셈횟수를 dp[3][8]에다가 업데이트를 시도하는 코드이다.

 

좀 더 자세하고 그림까지 있는 친절한 설명글은 다른글들을 구글링해서 참고하기를..