[10일차][dp2] 행렬의 곱셈시 최소 곱셈 수 구하기

- 문제 설명

A1부터 AN까지의 N개의 행렬을 곱하려고 함

A1이 1*2 행렬 A2가 2*3 행렬 A3이 3*2 행렬일때

(A1*A2)*A3을 하는경우 

((1*2)*(2*3)) *(3*2)

((1*3) * (3*2)) ->1*2*3으로 6번

(1*2) -> 1*3*2로 6번

총 12번을 하게 되고

A1*(A2*A3)을 하는 경우

(1*2)*((2*3) *(3*2))

((1*2) * (2*2)) ->2*3*2으로 12번

(1*2) -> 1*2*2로 4번

총 16번의 연산을 하게 되기 때문에

행렬 곱셈의 최소 횟수는 12다.

- 입력

1 // 테스트 케이스

3 // 행렬 3개

1 2 2 3 3 2 //1*2행렬, 2*3행렬, 3*2 행렬

- 출력

#1 12 // 테스트케이스, 행렬 곱셈의 최소 횟수

- 입력 예시

3
2
2 3 3 5
3
1 2 2 3 4 2
5
1 2 2 3 3 4 4 5 5 2

- 출력 예시

#1 30
#2 0
#3 48

- 코드

#include "stdio.h"

int numOfMul[11][11];

int p[11];

int N;

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        scanf("%d",&N);

        int n1, n2;

        scanf("%d %d",&n1,&n2);

        p[0] = n1;

        p[1] = n2;

        int checkError = 0;

        for(int i=2;i<=N;i++)

        {

            int n1, n2;

            scanf("%d %d",&n1,&n2);

            if(p[i-1] != n1) // 행렬을 곱할 수 없는 경우, 행렬 곱의 경우 n*m과 m*k 처럼 가운데가 같은 경우만 곱할 수 있다.

            {

                checkError = 1; // 에러라고 체크

                break;

            }

            else

            {

                p[i-1] = n1;

                p[i] = n2;

            }

        }

        int countOfMulti = 0;

        if(!checkError) // 에러가 아닌경우

        {

            for(int l = 1;l < N; l++) // l(엘)은 대각선으로 훑는 횟수

            {

                for(int i = 1; i <= N - l; i++)

                {

                    int j = i + l;

                    int min = 0x7fffffff; // min값 초기화

                    

                    for(int k = i; k < j; k++) // 행렬 곱셈이 가능한 경우의 수 모두를 돌면서

                    {

                        int calculNumOfMul = numOfMul[i][k] + numOfMul[k+1][j] + p[i-1]*p[k]*p[j]; //i~k까지의 행렬 곱셈횟수 + k+1~j까지 행렬 곱셈 횟수 + 현재 k의 행렬 곱셈 갯수

                        if(min > calculNumOfMul) // 계산한 값이 최소값이면

                        {

                            min = calculNumOfMul; // 갱신

                        }

                    }

                    numOfMul[i][j] = min; // 경우의 수 모두를 돌았을 때 최소값을 입력

                }

            }

            countOfMulti = numOfMul[1][N]; // 1~N개의 행렬을 곱한 횟수는 [1][N]에 저장됨

        }

        

        printf("#%d %d\n", tc,countOfMulti);

    }

    return 0;

}