[SWEA 1260] 화학물질 2

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN

 

풀이 :

 

완전탐색과 DP를 합쳐놓은 문제입니다.

 

우선 완전탐색으로 행렬을 찾고

연쇄행렬 최소곱셈 알고리즘을 사용하면 됩니다.(DP)

 

행렬을 찾는 과정은 제약 사항 중 부분 행렬의 열의 개수는 서로 다르며 행렬의 행의 개수도 서로 다르다는 조건에 따라

[SWEA 1259] 금속 막대 이 문제에서 설명 드린 것과 유사하게 찾을 수 있습니다.

 

N X M 행렬에서 N부분은 check 배열에서 ++, M부분은 check 배열에서 -- 하여 유일한 곱셈 순서를 찾고

연쇄행렬 최소곱셈 알고리즘을 사용합니다. (55 ~ 66라인)

연쇄행렬 최소곱셈 알고리즘 같은 경우에는 잘 정리된 글이 많아서 참고 링크에 올려 두겠습니다.

#include<stdio.h>
 
int t, n, arr[100][100],cache[20][20],check[101],mat[101],m[21],mcnt,front,rear;
#define Min(A,B) ((A)>(B)?(B):(A))
 
int main()
{
    scanf("%d", &t);
    for (int test = 1; test <= t; test++,mcnt=0)
    {
        printf("#%d ", test);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d", &arr[i][j]);
        for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)
        {
            if (arr[i][j])
            {
                int row, col;
                for (int ii = i;; ii++)
                {
                    if (!arr[ii][j])
                    {
                        col = ii - i;
                        check[row]++;
                        check[col]--;
                        mat[row] = col;
                        break;
                    }
                    for (int jj = j;; jj++)
                    {
                        if (!arr[ii][jj])
                        {
                            row = jj - j;
                            break;
                        }
                        arr[ii][jj] = 0;
                    }
                }
            }
        }
        for (int i = 1; i < 101; i++)
        {
            if (check[i] == 1)front = i;
            if (check[i] == -1)rear = i;
            check[i] = 0;
        }
        m[mcnt++] = front;
        while (1)
        {
            if (front == rear)break;
            front = mat[front];
            m[mcnt++] = front;
        }
        
        for (int L = 1; L < mcnt; L++)
        {
            for (int i = 1; i <= mcnt - L; i++)
            {
                int k = i + L;
                cache[i][k] = 987654321;
                for (int j = i; j < k; j++)
                {
                    cache[i][k] = Min(cache[i][k], cache[i][j] + cache[j + 1][k] + m[i - 1] * m[k] * m[j]);
                }
            }
        }
        printf("%d\n", cache[1][mcnt - 1]);
    }
}

[참고 링크]

http://yimoyimo.tk/MatrixMultiplication/