티스토리 뷰
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 |