Algorithm/BOJ

행렬 곱셈 순서 - 11049

jhg0406 2020. 3. 3. 17:12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//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);
}
 cs

 

 

 

 

 

 

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

 

11049번: 행렬 곱셈 순서

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

www.acmicpc.net

 

 

 

 

 

 

행렬 곱셈 순서

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)}