[백준 11049] 행렬 곱셈 순서

 

 DP 문제이다. 처음에 문제의 제목을 보고 슈트라센 알고리즘 문제인가 했는데, 열어보니 전혀 다른 문제였다. 어떤 수학적 원리에 의해 그리디 알고리즘으로 풀어낼 수도 있지 않을까 했는데, 고민해봐도 방법이 보이지 않아서 결국 정직하게 DP를 이용해서 해결했다.

 

 행렬이 N개 있다고 할 때, i번째 행렬부터 j까지의 행렬 곱셈 연산 횟수의 최솟값을 dp[i][j]이라고 두었다. 이 때 이 값을 구하기 위해서는 i~j번째 행렬을 두 부분으로 나누어 dp[i][mid] + dp[mid+1][j] + i번째 행렬의 행 * mid번째 행렬의 열(=mid+1번째 행렬의 행) * j번째 행렬의 열 값으로 구할 수 있을 것이다. 이 때 mid 값은 i부터 j까지 모두 확인해야 한다(만약 행렬 ABCD를 예시로 생각해보면 A(BCD), (AB)(BC), (ABC)D를 모두 확인할 필요가 있다). 여기서 점화식의 형태를 알아낼 수 있다.

 그렇다면 초기 값을 설정해주어야 하는데 dp[i][j]에서 i=j라면, 이 때 값은 0이된다. 행렬이 1개라면 행렬 곱셈이 일어나지 않기 때문이다. 이제 이 값을 이용해서 i와 j 사이의 거리를 0부터 N까지 늘려가면서 위의 점화식 형태로 dp 테이블을 채워나간다.

 

 모든 dp 테이블을 채우고 나면 dp[0][n-1] 값을 통해 행렬 곱셈 횟수의 최솟값을 얻을 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> matrix;

int main() {
    int n, r, c;
    cin >> n;

    matrix matrixList[500];

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

    int dp[500][500] = {0,};

    for(int len=1; len<n; len++) {
        for(int i=0; i+len<n; i++) {
            dp[i][i+len] = INT32_MAX;
            for(int mid=i; mid<i+len; mid++) {
                dp[i][i+len] = min(dp[i][i+len], dp[i][mid]+dp[mid+1][i+len]+matrixList[i].first*matrixList[mid].second*matrixList[i+len].second);
            } 
        }
    }

    cout << dp[0][n-1];
}