[백준 11049번] 행렬 곱셈 순서 (C++)

문제링크 : https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[501][2];
int dp[501][501];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        cin >> arr[i][0] >> arr[i][1]; //행, 렬
    }

    for(int i=1; i<N; i++) //범위의 크기
    {
        for(int j=1; j<=N-i; j++) //시작점 (j : 시작, k : 중간, i+j = 마지막)
        {
            dp[j][i+j]=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] + arr[j][0]*arr[k][1]*arr[i+j][1]);
            }
        }
    }

    cout << dp[1][N];

    return 0;
}

처음에는 간단해보였지만, 점화식을 떠올리기가 상당히 어려웠던 문제이다.

검색을 조금 하고 이해할 수 있었다.

 

먼저 예제 기준 계산식을 보면,

A*B : 5*3*2

AB*C : 5*3*2 + 5*2*6 이다.

<A : (5,3)>   <B : (3,2)>   <C : (2,6)>
   ***            **          ******
   ***            **          ******
   ***            **
   ***
   ***

 

 

dp[1][3]의 값은 행렬 1~3 까지의 곱 연산의 최소값이다.

기준점을 어디다 두느냐에 따라서 (1*2)*3일 수도 있고, 1*(2*3)일 수도 있다.

이 기준점(K) 조절을 통해서 최소값을 찾아나가야 한다.

 

문제에서 시작점이 j이고, 기준점이 k, 마지막이 i+j이다.

해당 문제의 경우 k가 2일 때 정답인데 이를 계산식으로 나타내면

dp[1][2] + dp[3][3]이다. [(1*2)*3]

그리고 dp[1][2]가 N*M이고, dp[3][3]이 M*K이다.

 

두 행렬의 곱셈은 N*M*K이므로 이에 대한 계산식이 arr[j][0]*arr[k][1]*arr[i+j][1]이다.

첫 구간 시작 부분의 행이 N : arr[j][0]
범위를 나눌 기준점 행의 렬이 M : arr[k][1]
범위 마지막 부분의 행렬의 K : arr[i+J][1]

 

우리가 구하는 것은 1~N까지의 곱 연산의 최소값이기에 해당 계산을 마친 dp[1][N]을 출력해주면 된다.