[백준] 행렬 곱셈 순서(11049)

문제 링크 : [백준] 행렬 곱셈 순서(11049)

문제 설명

n개의 행렬 사이즈가 주어질 때, 모든 행렬을 곱할 때, 곱셈 연산을 최소로 할 때의 연산 수를 출력하세요.

입력

N(행렬의 수, 1<=N<=500)
R_i C_i(R_i은 행렬의 행 수, C_i은 행렬의 열 수)

3
5 3
3 2
2 6

출력

최소 연산 수

90

카테고리

#DP

시간 복잡도 상한

O(N³)

해결 방법

1. 모든 순서를 다 해보기에는 TLE가 염려됩니다.
2. 각 구간 사이즈 별로 연산 횟수를 계산해놓고, 작은 단위의 행렬 곱셈 결과들을 확장해 나가는 방법을 생각해봅니다.
3. D[I][J]를 I번째 행렬부터 J번째 형렬까지의 곱셈 연산 횟수라고 정의합니다.(I<J)
4. 초기 데이터는 인접한 다음 행렬과의 곱을 계산합니다.
   4-1. D[I][I+1]=IN[I][0]IN[I][1]IN[I+1][1]
5. D[I][J] = 모든 K(1<=K<J)에 대하여,
   D[I][K]+D[K+1][J]+IN[I][0]+IN[K][1]+IN[J][1] 중 가장 작은 값이 됩니다.
   5-1. 위 식은 행렬의 곱셈의 성질입니다. 자세한 내용은 아래 링크를 참고해주세요.
   행렬 곱셈
6. 코드에서는 입력값에 대하여 2차원 배열로 저장할 필요가 없어 1차원 배열로 변경하여 저장하였습니다.

시간복잡도

O(N³)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
int n,d[501],e[500][500],i,j,k,l,t;
int main(){
    scanf("%d",&n);
    scanf("%d%d",d,d+1);
    for(i=2;i<=n;i++)scanf("%*d%d",d+i);
    for(i=0;i<n-1;i++)e[i][i+1]=d[i]*d[i+1]*d[i+2];
    for(l=2;l<n;l++){
        for(i=0;i<n-l;i++){
            for(j=i+l,k=i;k<j;k++){
                t=e[i][k]+e[k+1][j]+d[i]*d[k+1]*d[j+1];
                if(!e[i][j]||e[i][j]>t)e[i][j]=t;
            }
        }
    }
    printf("%d",e[0][n-1]);
}