11049 행렬 곱셈 순서 (동적계획법) [Gold III]

11049번: 행렬 곱셈 순서 (acmicpc.net)

동적 계획법

 

N개의 행렬을 곱하는 순서를 다르게 하여 가장 적은 곱셈 연산수를 찾는 문제입니다.

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

AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.
같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

 

풀이법

N이 4라고 가정하겠습니다.

이때 행렬 연산의 경우의 수를 나열해보면 아래와 같습니다.

(1)* (234) - 2~4를 연산하는 경우의 수는 재귀를 통해 작은 문제로 만들어 해결합니다.

(12)* (34)

(123)* (4)

 

즉 반복문을 통해서 행렬을 왼쪽과 오른쪽으로 나누면 모든 경우의 수에 대해서 계산할 수 있을 것 같습니다.

왼쪽 행렬들을 하나의 행렬로 만드는데 사용된 연산의 수 + 

오른쪽 행렬들을 하나의 행렬로 만드는데 사용된 연산의 수 + 

왼쪽 행렬, 오른쪽 행렬을 하나로 만다는데 사용되는 연산 수

이후에 위의 방식으로 연산 수를 계산하여 최소값을 찾아주면 됩니다. 

 

흠.. 너무 어렵다 생각한 문제였는데 막상 풀이법 쓰고나니까 별거 없네요ㅋㅋ

결국은 풀이법을 생각할 수 있는가 아닌가의 문제인 것 같습니다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

static int N;
static vector<pair<int, int>> M;
static long D[502][502];
int execute(int s, int e);

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        std::cout.tie(NULL);

        cin >> N;
        M.resize(N + 1);
        
        for (int i = 0; i < N + 1; i++)
        {
                for (int j = 0; j < N + 1; j++)
                        D[i][j] = -1;
        }

        for (int i = 1; i <= N; i++)
        {
                int y, x;
                cin >> y >> x;
                M[i] = make_pair(y, x);
        }
        cout << execute(1, N) << "\n";  
}

 

int execute(int s, int e)
{
        int result = 1000000000;
        if (D[s][e] != -1)
                return D[s][e]; 
         
        if (s == e)
                return 0;

        if (s + 1 == e) 
                return M[s].first * M[s].second * M[e].second;   
        
          
        for (int i = s; i < e; i++)
        {
                result = min(result, M[s].first* M[i].second* M[e].second + execute(s, i) + execute(i + 1, e));
        }
         
        return D[s][e] = result;
}