백준 11049 행렬 곱셈 순서

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

이 문제는 개인적으로 좋은 문제라고 생각한다. 또한 나에게 분할정복과 다이나믹 프로그래밍에 대한 많은 깨달음을 준 문제이기도 하다. 상당한 난이도가 있다고도 생각된다.

 

일단 곱셈이 이루어질 2개의 행렬 A, B가 있을 때, A의 행의 수와 B의 열의 수와 A의 열의 수(=B의 행의 수)의 곱이 두 행렬의 곱에서 발생하는 곱셈 횟수가 된다. 행렬 ABCDEF가 주어질 경우, 앞에서부터 순서대로 곱해나가도 되지만, A(BC)((DE)F)처럼 순서를 마구 섞을 수도 있다. 문제에서 잘 관찰해야 할 점은 어떤 부분 곱을 구해도 문제의 입력은 항상 행렬들이 체인처럼 연결되어있기에, 곱셈의 결과행렬은 앞뒤의 이웃 행렬들과 연결된다. 아래의 그림을 보자.

memo라는 2차원DP를 만들어둔다. memo[s][e]는 s번째(인덱스) 행렬에서 e번째 행렬까지의 곱셈 횟수 중 최소 횟수를 의미한다.

그리고 memo[s][e]는 memo[s][i]와 memo[i+1][e]로 나누어서도 계산할 수 있는데 (뒤의 행렬들을 먼저 곱할 수도 있으므로) 이때 각 부분 곱들, memo[s][i]와 memo[i+1][e]의 곱이 만드는 곱셈 횟수까지 추가적으로 더해주어야 한다. 즉, 위의 그림의 내용을 다시 쓰면

memo[s][e]=memo[s][i]+memo[i+1][e]+mat[s][0]*mat[i][1]*mat[e][1]

위와 같이 되고, 이것이 바로 문제 해결의 점화식이 된다. mat배열은 입력으로 주어진 각 행렬들의 행과 열을 저장하는 곳이다.

mat[i][0]은 i번째 행렬의 행의 개수이고 mat[i][1]은 열의 개수이다.

 

<주요 내용>

재귀 함수, DP, 분할 정복, 메모이제이션, 행렬 연산

 

<코드>

s에서 시작하여 e까지 루프를 돌면서 서로 다른 모든 순서로 연산되는 행렬 곱셈 횟수를 파악하고 그중의 최솟값을 취하여 기록해두고 리턴한다. 모든 경우의 수를 탐색하여 최소값을 갱신 후 리턴하므로 리턴값은 항상 최소 횟수임이 보장된다.

#include <iostream>
#define endl '\n'
using namespace std;

const int sz=5e2+1;
int mn,m,mat[sz][2],memo[sz][sz];

int solve(int s,int e){
    int ret=0;
    if(s==e)return 0;
    if(memo[s][e])return memo[s][e];
    if(e==s+1){
        ret=mat[s][0]*mat[s][1]*mat[e][1];
        memo[s][e]=ret;
        return memo[s][e];
    }
    for(int i=s;i<e;++i){
        ret=solve(s,i)+solve(i+1,e)+mat[s][0]*mat[i][1]*mat[e][1];
        if(!memo[s][e]||ret<memo[s][e])memo[s][e]=ret;
    }
    return memo[s][e];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>m;
    for(int i=0;i<m;++i)cin>>mat[i][0]>>mat[i][1];
    mn=solve(0,m-1);
    cout<<mn<<endl;
    return 0;
}