[C++] 백준 11049번 : 행렬 곱셈 순서 (G3)

#문제

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

#풀이 & 학습한 내용

행렬 사이의 곱셈에 순서대로 숫자를 부여한 뒤에, M[i][j]가 Ai부터 Aj까지의 곱에서의 최소 곱셈수를 의미하도록 했다. M[i][j]를 마지막 곱셈이 이루어진 곳을 의미하는 k가 i부터 j-1까지 값을 가질때, (M[i][k] + M[k+1][j]+ 마지막곱셈에서의 곱셈수)중 최소 값을 갖게 Optimal substructure를 구현했다. dp의 주요 개념인 메모이제이션을 생각하며 코딩했으며, 만약 메모지제이션을 하지 않고 함수 호출을 한다면 시간초과로 문제가 해결되지 않는다.

또한, 이 문제를 통해 dp에서 테이블의 basis를 넣은 뒤 table을 채우는 순서에 대해 고민해 볼 수 있었다. 테이블의 값을 채우려면 그 왼쪽부분과 아래쪽부분에 대한 정보가 필요한 점을 예시를 통해 파악하고, for문을 구성했다.

 

#소스코드

#include<iostream>
 
#define INT_MAX 2147483647
 
using namespace std;
int d[502];
int M[502][502];
 
int find_matrix(int i, int j);//Ai부터 Aj까지의 곱에서 최소 곱셈수를 반환
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N;
    int trash;
    cin >> N;
    cin >> d[0];
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
        if (i < N)
            cin >> trash;
    }
 
    for (int i = 1; i <= N ; i++) {
        M[i][i] = 0;
    }
    //table에 basis넣기(setup)
 
    for (int j = 2; j <= N; j++) {
        for (int i = j-1; i >= 1; i--) {
            M[i][j] = find_matrix(i, j);
        }
    }
    //적절한 순서에 따라 table채우기(fill)
 
    cout << M[1][N] <<"\n";
}
 
int find_matrix(int i, int j) {
    if (i == j)
        return 0;//행렬이 하나일땐 필요한 곱셈수 0
    else {
        int min = INT_MAX;
        int temp;
        for (int k = i; k <= j - 1; k++) {
            if ((temp = M[i][k] + M[k+1][j] + d[i - 1] * d[k] * d[j]) < min) {
                min = temp;
            }
        }
        M[i][j] = min;
        return M[i][j];
    }
}