알고리즘 문제
[C/C++ 백준 11049번] 행렬 곱셈 순서 (Gold 3)
새파란 공대생
2020. 12. 11. 20:12
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
모든 경우를 다 구해서 dp행렬에 저장해야한다.
0 ~ N-1 까지의 행렬의 곱을 구한다고 가정했을 때, 0 ~ k, k+1 ~ N-1의 두 가지 경우로 나누어 곱셈 연산의 수를 비교해보자.
3중 for문을 돌릴 때, 돌리는 순서에 유의해야 한다. 각 dp마다 어떤 dp값이 필요한지 생각하면서 사용하자.
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
int dp[501][501];
int main(void){
int N, r[501], c[501];
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d %d", &r[i], &c[i]);
}
for(int i=0; i<N; i++){
dp[i][i] = 0;
}
for(int b=1; b<N; b++){
for(int i=0; i<N-b; i++){
int j= i+b;
dp[i][j] =INT_MAX;
for(int k=i; k<j; k++)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+r[i]*r[k+1]*c[j]);
//printf("%d %d : %d\n",i,j,dp[i][j]);
}
}
printf("%d", dp[0][N-1]);
}