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

문제

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

11049번: 행렬 곱셈 순서

풀이 과정

[참고 링크]

해당 문제는 11066 파일 합치기 문제와 매우 유사하다. 파일 합치기 문제를 풀이했을 때 사용했던 알고리즘과 동일한 구조로 동작하도록 구현하기 위해 위의 링크를 참고했다. 해당 문제와 동일한 블로그의 포스팅이다. 설명이 매우 자세하고 충분히 이해하고 DP를 적용한 코드를 사용할 수 있었다.

 

해당 포스팅을 보고 공부 중 어려웠던 부분을 다른 사람들이 더 이해하기 쉽도록 예시를 들어 설명하고 마치려고 한다.

 

3중 for 문의 동작은 아래와 같다.

i : 곱셈 연산에 참여한 행렬 수
j : 곱셈 시작 행렬의 번호
k : 시작점 j부터 i+j 위치까지 탐색을 위한 변수
해당 for 문은 j부터 시작하여 i+j까지의 행렬의 곱셈의 최솟값을 구한다.

 

연산 과정)

k는 j부터 j + i까지 반복된다.
k 가 j 일 때, dp [j][j] + dp [j+1][i+j] + m [j][0]*m [k][1]*m [i+j][1]와 비교
k 가 j + 1 일 때, dp [j][j+1] + dp [j+1+1][i+j] + m [j][0]*m [j+1][1]*m [i+j][1]와 비교
k 가 j + 2 일 때, dp [j][j+2] + dp [j+2+1][i+j] + m [j][0]*m [j+2][1]*m [i+j][1]와 비교
...
k 가 j + i 일 때, dp [j][j+i] + dp [j+i+1][i+j] + m [j][0]*m [j+i][1]*m [i+j][1]와 비교

 

 

 

DP의 본질은 Divide and Conquer이다. 결국 분할 정복을 통해 이전의 반복을 최소화하는 것에 있다.

여러 행렬의 곱은 결국 두 개의 곱, (행렬 A)와 (행렬 B)의 곱으로 나눌 수 있다.라는 생각을 하면 이해하는데 도움이 될 것 같다.

 

예시)

j = 3, i = 4 -> dp [3][7] -> 행렬 3 ~ 행렬 7까지의 곱 연산의 최소 값을 의미한다.

해당 연산은 빨간색으로 표시된 행렬을 기준으로 좌, 우로 나누어 곱셈을 하는 경우를 의미한다.

행렬 3 X 행렬 4 X 행렬 5 X 행렬 6 X 행렬 7을 두 개의 행렬 곱으로 나눌 수 있는 경우의 수이다.

3 / 4567

34 / 567

345 / 67

3456  /7

이렇게 각각을 DP에 저장되어 있는 최솟값을 이용하여 비교하며 업데이트한다. 해당 연산은 현재 5개 크기의 행렬 곱을 수행 중이다.

 

DP는 작은 단위부터 계산되어 저장했다. 따라서 이미 1개 크기, 2개 크기, 3개 크기, 4개 크기의 행렬 곱들의 최솟값을 알기 때문에 5개 크기의 행렬 곱도 구할 수 있게 된다. 이 과정을 반복하여 DP를 채우고 나면 1번부터 n번까지의 행렬 곱의 최솟값을 구하면 답을 얻을 수 있다.

 

 

소스 코드

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int n;
const int max_n = 501;
int m[max_n][2];

//dp[a][b] = k 의 의미는 a 부터 b 번째 행렬을 연산했을 때의 최솟값이 k임을 의미한다.
int dp[max_n][max_n];


int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> m[i][0] >> m[i][1];
    }

    /*
     * i : 곱셈 연산에 참여한 행렬 수
     * j : 곱셈 시작 행렬의 번호
     * k : 시작점 j 부터 i+j 위치까지 탐색을 위한 변수
     * 
     * 해당 for 문은 j 부터 시작하여 i+j 까지의 행렬의 곱셈의 최솟값을 구한다.
     * 
     * dp[j][i+j] 의 값은 아래의 연산을 통해 구해진다.
     * k 는 j 부터 j + i 까지 반복된다.
     * 
     */
    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] + m[j][0]*m[k][1]*m[i+j][1]);
            }
        }
    }

    cout << dp[1][n];

    return 0;
}

 

결과 및 후기

비슷한 문제를 풀었음에도 해당 코드를 구현하는 것이 그리 순탄치 않았다. 그래서 다른 사람의 블로그를 보고 풀이를 참고했지만 이번 포스팅을 통해 더 많은 것을 깨달은 느낌이다.