백준 11049 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

 

 

 

EXPLANATION

 

입력값으로 주어지는 행렬들은 서로 순서가 인접한 행렬들만 곱할 수 있음.

 

(현재 두 행렬을 곱해서 한 행렬을 만들기 까지, 필요한 총 곱셈 연산 횟수)

= (각 두 행렬을 만드는데 필요했던 각각의 총 곱셈 연산 횟수의 합) + (현재 두 행렬을 곱할 때 필요한 곱셈 연산 횟수)

 

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

BC를 먼저 곱하고 A를 곱하는 경우.

 

B와 C를 곱한다.

36 = (0 + 0) + (3×2×6)

현재 두 행렬을 곱해서 한 행렬을 만들기 까지, 필요한 총 곱셈 연산 횟수: 36

 

A와 BC를 곱한다.

126 = (0 + 36) + (5×3×6)

현재 두 행렬을 곱해서 한 행렬을 만들기 까지, 필요한 총 곱셈 연산 횟수: 126

 따라서, 최종의 한 행렬을 만든데 필요한 총 곱셈 연산 횟수는 126이다.

 

행렬을 곱해서 합쳐진 범위가 2인거부터 오름차순으로 dp에 넣어야 더 큰 범위를 나타내는 dp 값을 할당할 때, 이전의 더 작은 범위의 dp값을 이용할 수 있다. (합치는 범위가 1이면 안합친거므로 곱셈 연산 횟수 0)합치는 범위가 정해졌으면, 범위의 시작을 정하고, 이후, 그 범위를 두 부분으로 나누는 기준을 정한다.이에 대한 정보를 index로 가지는 dp에 이에 대한 합치는데 필요한 총 곱셈 연산 횟수를 할당한다.

for (int i = 1; i < N; i++)
{
    for (int j = 1; i + j <= N; j++)
    {
        dp[j][i + j] = INF;
        for (int k = j; k <= i + j; k++)
        {
            dp[j][i + j] 
            = min(
                dp[j][i + j], 
                dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i+j][1]);	
                //N*M행렬과 M*K행렬을 곱할 때 곱셈의 연산 횟수: N*M*K.S
        }
    }

}

참고: https://cocoon1787.tistory.com/317

 

CODE

#include<iostream>
#include <limits.h>
using namespace std;

int N, r, c;
int sum[501], matrix[501][2], dp[501][501];

int main()
{
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> r >> c;
        matrix[i][0] = r;
        matrix[i][1] = c;
    }

    for (int i = 1; i < N; i++)
    {
        for (int j = 1; i + j <= N; j++)
        {
            dp[j][i + j] = INT_MAX;
            for (int k = j; k <= i + j; k++)
            {
                dp[j][i + j] 
                = min(
                    dp[j][i + j], 
                    dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i+j][1]
               );
            }
        }

    }

    cout << dp[1][N];

}