문제

문제 분석

Naive 하게 풀면 (N-1)! 순서대로 연산을 시도해보는 것이다.
그러나 이는 시간 복잡도에 문제가 있다.

그러나 이 Naive한 케이스들 실행하는 과정을 잘 살펴보면,
결국 마지막엔 왼쪽 행렬과 오른쪽 행렬을 곱하는 게 마지막이다.
그럼 왼쪽 행렬은 어디서 왔나 생각해보면 다시 왼쪽 덩어리와 오른쪽 덩어리의 곱셈 결과이다.

예를 들어, N = 10일 때 아래와 같은 연산 순서로 진행됐을 수 있다.

	[1, 5]	x 	[6,10]
    /   \		/	\
 [1,3] [4,5] ...

이때, 아래 케이스를 살펴보면, 반복적으로 조사하는 부분이 생기는 걸 알 수 있다.

	[1,7] 	x	[8, 10]
    /	\		/	\
 [1,3] [4,7]...
 		/ \
  ..[4,5] [6,7]..

dp[LeftIdx][RightIdx] = maxCase 형태로 풀 수 있다.

알고리즘

• Dynamic Programming

자료구조

• 2d vector

결과

• 성공

/*
행렬 곱의 시작부터 마무리 방향으로 관찰했더니 아이디어가 잘 안 떠올랐다.
마무리 단계부터 생각하니 아이디어가 떠올랐다.
일단, Naive한 방법으로 상황을 적어보고, 시작부터 보는 것 뿐만 아니라, 뒤에서부터도 살펴보자
*/

#include <iostream>
#include <vector>
using namespace std;

struct Vec2{
    int r,c;
};
struct TableData{
    Vec2 size;
    int minNumOfOp;
};

const int MAX_INT = ~(1<<31);

int N;
vector<vector<TableData>> table;

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    // Input
    cin >> N;
    table.resize( N, vector<TableData>(N, TableData{Vec2{0,0},0}));
    for ( int i = 0; i < N; i++ ){
        int r, c;
        cin >> r >> c;
        table[i][i] = TableData{ Vec2{r, c}, 0 };
    }

    // Build table
    for( int loop = 1; loop < N; loop++ ){
        for ( int l = 0; l < N; l++ ){
            int r = l + loop; 
            if ( r >= N )
                continue;
            TableData min = TableData{ Vec2{0,0}, MAX_INT};
            for ( int mid = l; mid < r; mid++ ){
                TableData left = table[l][mid];
                TableData right = table[mid+1][r];
                TableData newD;
                /*
                cout << "l, mid, r" << l << " " << mid << " " << r << endl;
                cout << "left: " << left.size.r << " " << left.size.c << " " << left.minNumOfOp << "\n";
                cout << "right: " << right.size.r << " " << right.size.c << " " << right.minNumOfOp << "\n";
                */
                newD.size.r = left.size.r;
                newD.size.c = right.size.c;
                newD.minNumOfOp = left.minNumOfOp + right.minNumOfOp +
                    (left.size.r * left.size.c * right.size.c);
                if( min.minNumOfOp > newD.minNumOfOp ){
                    min.minNumOfOp = newD.minNumOfOp;
                    min.size = newD.size;
                }
            }
            table[l][r] = min;
        }
    }
/*
    for ( int r = 0; r < N; r++ ){
        for ( int c = 0; c < N; c++ ){
            cout << table[r][c].minNumOfOp << " ";
        } cout << "\n";
    }*/

    // Ans minimun number of operations
    cout << table[0][N-1].minNumOfOp;

    return 0;
}

Other