행렬 곱셈 순서 - 11049

//11049 - 행렬 곱셉 순서
 
#include <iostream>
#include <limits>
using namespace std;
 
#define INF INT32_MAX
int N;
int R[500];
int C[500];
int cache[500][500];
 
void init()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        cin >> R[i] >> C[i];
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            cache[i][j] = -1;
}
 
int cal(int start, int mid, int end)
{
    return R[start]*C[mid]*C[end];
}
 
int dp(int start, int end)
{
    if(start == end) return 0;
    int& ret = cache[start][end];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int mid = start; mid<end; ++mid)
        ret = min(ret, dp(start, mid) + dp(mid+1, end) + cal(start, mid, end));
    return ret;
}
 
int main()
{
    init();
    cout << dp(0, N-1);
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

 

 

 

 

 

행렬 곱셈 순서

DP문제 입니다.

C(i, j) : i~j 까지의 행렬을 곱하는 비용의 최소값

D(i, k, j) : i~k까지의 행렬들이 곱해진 행렬과 k+1~j까지의 행렬들이 곱해진 행렬을 곱하는데 드는 비용

C(i, j) = min(i < j < k){C(i, k) + C(k+1, j) + D(i, k, j)}