[BOJ 11049] 행렬 곱셈 순서(C++)

행렬 곱셈 순서 (Gold 3)

문제

전체 문제 보기

11049번: 행렬 곱셈 순서

접근법

이번 문제는 BOJ11066 파일 합치기 문제와 거의 동일합니다. 파일 합치기 문제를 풀이한 적이 있기 때문에 접근법에 대한 설명은 파일 합치기 풀이로 대신합니다. 이번 문제와 파일 합치기 문제와의 차이만 살펴보면, 이번 문제에서는 연속된 행렬의 곱을 최소화해야 한다는 점입니다. 그래서 행렬의 임의의 위치 p에서 p + k까지 곱한 행렬 A와 p + k+1에서 p + n까지 곱한 행렬 B를 곱할 때 곱셈의 횟수는 (p의 row 개수) * (p+k의 row 개수) * (p + n - 1의 col 개수)으로 나타낼 수 있습니다.

 

그리고 파일 합치기 풀이에서는 std::vector를 활용하여 2차원배열을 만들고 풀이를 했지만 이번에는 std::array를 활용하여 2차원 배열을 사용하였습니다. std::vector는 2차원 배열이 항상 메모리 공간에 연속됨이 보장되지 않지만, std::array는 2차원 배열의 모든 원소가 항상 메모리에 연속됨이 보장되기 때문에 캐시라인의 효율을 더욱 높일 수 있습니다. std::vector를 std::array로 변경하여 52ms가 걸리던 시간을 44ms로 줄여 8ms 단축할 수 있었습니다.

전체 구현

다음과 같이 \(O(n^2)\) 시간 복잡도로 계산할 수 있습니다.

#include <iostream>
#include <array>
#include <algorithm>
#define endl '\n'
const int INF = 987'654'321;
struct Matrix {
    int row;
    int col;
};
int main()
{    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    int N; // 행렬의 개수 N(1 ≤ N ≤ 500)
    std::cin >> N;
    std::array<Matrix, 500> matArr;
    std::array<std::array<int, 501>, 501> dp{ };
    for (auto& row : dp)
    {
        row.fill(INF);
    }

    for (int i = 0; i < N; ++i)
    {
        std::cin >> matArr[i].row >> matArr[i].col;
    }

    //dp[1][i]: i위치에서 1개 행렬을 선택할 경우 곱셈수: 항상 0
    for (int i = 0; i < N + 1; ++i)
    {
        dp[1][i] = 0;
    }

    //dp[n][p]: p위치에서 n개일때 최솟값
    for (int n = 2; n < N + 1; n++)
    {
        for (int p = 0; p + n < N + 1; p++)
        {
            for (int k = 1; k < n; ++k)
            {
                int a = dp[k][p] + dp[n - k][p + k] + (matArr[p].row * matArr[p+k].row * matArr[p + n - 1].col);
                dp[n][p] = std::min(dp[n][p], a);
            }
        }
    }
    std::cout << dp[N][0];
    return 0;
}