A응실 화학물질2 / 디피

1. 디피 문제 풀기 2. 화학물질 위치 찾기 2. 순서대로 세우기 3. 다음으로 디피를 사용해서 가장 곱이 작은 값을 찾아내기 4. 이것을 표로 만들어서 어떻게 곱해 나갈 것인지 확인 필요

#include <stdio.h> //#define MAX 101 #define MAX 10 int T, t, N; int map[MAX][MAX]; 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; }