[BOJ] 11049번 - 행렬 곱셈 순서

백준 11049번 - 행렬 곱셈 순서

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	12013	5537	3943	44.219%

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 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개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 2^{31}-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 ${2^{31}}$-1보다 작거나 같다.

 

---

예제 입력 1

3
5 3
3 2
2 6

예제 출력 1

90

출처

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

알고리즘 분류

• 다이나믹 프로그래밍

접근 방법

결국 이 문제는 괄호를 적절히 쳐서 계산하는 문제이다. 가장 쉽게 떠올릴 수 있는 방법은 괄호를 치는 모든 방법에 대해서 연산 값을 구하는 완전탐색이라는 방법이 있겠다. 하지만 이 경우 ${2^{500/2}}$ 의 연산이 필요한데, 이것은 절대 시간제한 내에 풀 수 없는 연산이다.

 

먼저, 괄호 치기라는 틀 안에서 문제를 바라보자.

행렬 A,B,C 에 대해서 우리가 괄호를 칠 수 있는 경우는 다음과 같을 것이다.

 

1. (A)(B)(C)

2. (AB)(C)

3. (A)(BC)

 

이것을 더 확장 시켜서 A,B,C,D라는 행렬에 대해서 괄호를 치는 경우를 생각해보자.

1. (A)(B)(C)(D)

2. (AB)(CD)

3. (ABC)(D)

... (이하 생략)

 

ABCD의 행렬 곱의 가능한 연산은 결국 작은 부분들의 조합인 것이 보이지 않는가?

이하, 괄호를 친 단위를 덩어리라고 표현하겠다.

 

ABCDEF... 의 행렬 곱은 더 작은 덩어리들의 조합이다.

즉 어떠한 행렬 곱의 형태도 (sub) * (sub) 로 표현 된다는 것이다.

 

이 정보를 활용하기 위해서 메모이제이션 배열을 다음과 같이 정의하자.

DP[l][r] = [l,r]까지의 부분 행렬을 고려하였을 때 나올 수 있는 행렬 곱의 최소 연산 횟수  (l, r은 인덱스 l<=r )

이제 점화식을 세워보자.

먼저 DP를 위와 같이 정의하였을 때 우리가 구하고 싶은 최적해는 DP[0][N-1]일 것이다.

특정 부분 행렬의 최소 연산 횟수를 구하기 위해서, 크기가 더 작은 부분 행렬 부터 고려해주자.

(bottom - top 방식으로 memoization) 

기초 연산이 되는 부분은 l + 1 == r 이 되는 부분이다. ( 두 행렬의 곱 ) < Base Case >

 

어떤 행렬도 (sub) * (sub) 로 표현 되는 것을 이용해 2개의 sub matrix로 분할해준다.

분할을 위해서 m이라는 변수를 도입하여 [left, m] * [m+1, right] 로 표현 되는 것 중 가장 연산 횟수가 작은 것으로 초기화 시켜주면 우리가 원하는 전체 행렬의 최적해도 구할 수 있다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> N ;

    vector<int> r(N), c(N);

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

    // 하나의 덩어리는 크기가 더 작은 덩어리들로 분할이 가능하다.
    int dp[501][501] = {0, };
    // base AB, BC 등 2개의 행렬이 묶일 때
    for(int i=0; i<N-1; i++){
        dp[i][i+1] = r[i] * r[i+1] * c[i+1];
    }

    // [left, right] 의 인덱스 차이 = gap
    for(int gap = 2; gap < N ; gap++){
        for(int left=0; left < N-gap; left++){
            int right = left + gap;
            // [left ~ right] 의 연산 횟수의 최솟값
            for(int m = left ; m < right ; m++){
                // [left, m] 의 크기 : r[left] x c[m]
                // [m+1, right] 의 크기 : r[m+1] x c[right]
                // 문제 조건에 따라, c[m] == r[m+1]
                int res = dp[left][m] + dp[m+1][right] + r[left] * c[m] * c[right];
                if( dp[left][right] == 0 || dp[left][right] > res )
                    dp[left][right] = res;
            }
        }
    }
    cout << dp[0][N-1];
    return 0;
}