화학물질2

1. 화학물질2

2. DP 문제

3. DP 연습

4. 아니, 그전에 재귀 이런 문제도 있구나 오케이

#include <stdio.h>

int T, t, N;
int map[101][101];
typedef struct matrix {
    int r, c;
}M;
M result[30], order[30];
int size, cnt;
int dp[30][30];

int main() {
    freopen("input.txt", "r", stdin);
    int i, j, k, l;
    int headidx = 0; // 앞머리 인덱스

    scanf("%d", &T);
    while (t++ < T) {
        size = cnt = 0;
        scanf("%d", &N);
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++)
                scanf("%d", &map[i][j]);
        }
        //각각의 화학물질 찾기
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    for (k = 0; k < N; k++) {
                        if (map[i + k][j] == 0) break;
                        for (l = 0; l < N; l++) {
                            if (map[i + k][j + l] == 0) break;
                            map[i + k][j + l] = 0;
                        }
                    }
                    result[size].r = k;
                    result[size].c = l;
                    size++;
                }
            }
        }
        //앞 머리 찾기
        for (i = 0; i < size; i++) {
            for (j = 0; j < size; j++) {
                if (i != j && result[i].r == result[j].c) break;
            }
            if (j == size) headidx = i;
        }
        order[cnt].r = result[headidx].r;
        order[cnt].c = result[headidx].c;
        cnt++;
        // 순서대로 다시 저장
        for (i = 0; i < size; i++) {
            for (j = 0; j < size; j++) {
                if (result[headidx].c == result[j].r) {
                    headidx = j;
                    order[cnt].r = result[headidx].r;
                    order[cnt].c = result[headidx].c;
                    cnt++;
                    break;
                }
            }
        }
        int tempdp = 0;
        //대각선 dp채우기
        for (i = 1; i < size; i++) { // 시작점 column 값 
            for (j = 0; j < size - i; j++) { // 대각선 테이블 채우는 갯수
                if (i == 1)
                    dp[j][i + j] = order[j].r*order[j].c*order[i + j].c;
                else {
                    dp[j][i + j] = 1000000000;
                    for (k = j; k <= i + j - 1; k++) {
                        tempdp = dp[j][k] + dp[k + 1][i + j] + (order[j].r)*(order[k + 1].r)*(order[i + j].c);
                        dp[j][i + j] = tempdp > dp[j][i + j] ? dp[j][i + j] : tempdp;
                    }
                }
            }
        }
        printf("#%d %d\n", t, dp[0][size - 1]);
    }
    return 0;
}