티스토리 뷰

Algorithm/BOJ

11049 행렬 곱셈 순서

henry1214 2019. 10. 16. 19:07

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

 

11049번: 행렬 곱셈 순서

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

www.acmicpc.net

 

d[x][y] = x번째 행렬부터 y번째 행렬까지 곱했을 때 곱셈 연산의 최소값

 

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
#include <cstdio>
 
int n,a[500][2],d[500][500];
 
int go(int x,int y)
{
    if(d[x][y]) return d[x][y];
    if(x==y) return 0;
    if(x+1==y) return a[x][0]*a[x][1]*a[y][1];
    int &ans=d[x][y];
    ans=987654321;
    for(int k=x;k<y;k++)
    {
        int t=go(x,k)+go(k+1,y)+a[x][0]*a[k][1]*a[y][1];
        if(ans>t) ans=t;
    }
    return ans;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d %d",&a[i][0],&a[i][1]);
    printf("%d",go(0,n-1));
    return 0;
}
cs

'Algorithm > BOJ' 카테고리의 다른 글

8/21 Problem Solving  (17) 2024.08.21
5573 산책  (0) 2023.11.22
2133 타일 채우기  (0) 2019.10.13
12969 ABC  (0) 2019.10.13
1328 고층 빌딩  (0) 2019.10.13
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday