1260. [S/W 문제해결 응용] 7일차 - 화학물질2

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN#none

 

문제 풀이:

1. 0이 아닌 직사각형들 찾기 

2. 행렬들을 곱셈 가능한 순서로 나열

  -> "1259. [S/W 문제해결 응용] 7일차 - 금속막대" 문제와 동일한 풀이법 

  -> 이 블로그의 풀이를 참고하였습니다.

3. 연쇄 행렬 최소 곰셈 알고리즘 사용

  -> 2019/11/22 - [알고리즘/기타] - [BOJ] 11049 행렬 곱셈 순서

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#define inf 987654321
using namespace std;

typedef pair<int, int> P;
vector<P> v;

int tc, n,arr[102][102],back[102],check[102],d[102],dp[102][102];
void func2(int x, int y);
void func() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] != 0) {
				if(i > 0 && arr[i - 1][j] != 0) continue;
				if (j > 0 && arr[i][j - 1] != 0) continue;
				func2(i, j);
			}
		}
	}
}
void func2(int x, int y) {
	int curx = x;
	while (curx < n&&arr[curx][y] != 0) {
		curx++;
	}
	int cury = y;
	while (cury < n &&arr[x][cury] != 0) {
		cury++;
	}
	v.push_back({ curx - x, cury - y });
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cin >> n;
		v.clear();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}
		func(); // 행렬 찾기

		int sz = v.size();
		for (int i = 0; i < sz; i++) {
			back[v[i].first] = v[i].second;
			check[v[i].first]++;
			check[v[i].second]--;
		}
        // check가 0이면 중간에 속하는 금속임을 나타냄
        // check==1 : 제일 앞에 있는 금속이다
        // check==-1 : 제일 뒤에 있는 금속이다
		int front;
		for (int i = 0; i <= n; i++) {
			if (check[i] == 1) front = i;
			check[i] = 0;  // check 배열 초기화
		}
		for(int i = 0; i < sz; i++) {  // 정렬된 행렬의 값 얻어내기
			d[i] = front;
			front = back[front];
		}
		d[sz] = front;

		for (int diagonal = 0; diagonal <sz; diagonal++) {
			for (int i = 1; i <= sz - diagonal; i++) {
				int j = i + diagonal;
				if (i == j) continue;
				dp[i][j] = inf;
				for (int k = i; k < j; k++) {
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j]);
				}
			}
		}
		cout <<"#"<<t<<" "<< dp[1][sz] << '\n';
	}
	return 0;
}