[BAE/<JOON> 문제풀이] 1028. 다이아몬드 광산

https://www.acmicpc.net/problem/1028

1028번: 다이아몬드 광산

---

서론::

이게 왜 DP 일까 ?

설마 부분합 구하는 그 부분 때문에 DP라고 하는건 아니겠지 ?

아니면 DP를 이용하는 풀이가 따로 있는 걸지도 모르겠다.

---

아이디어::

문제를 보자마자 떠오르는 아이디어는 비숍 문제에서 봤던 대각선을 수직선으로 치환하는 방법이었다.

( 짝수 행렬과 홀수 행렬은 서로에게 영향을 미치지 않으므로 시작부터 이 둘을 구분한 2개의 배열을 만들고 풀이를 진행한다. )

두 행렬을 만들고 거기에 어떤 DP 알고리즘을 적용하면 답을 찾을 수 있을 거라고 생각했다.

이 방법의 문제는 시간안에 동작하는 "어떤 DP 알고리즘"을 찾지 못했다는데에 있다. 분명 있을 것 같은데 못 찾음...

DP 로 풀려면 작은 다이아를 검출했을 때 그걸 합쳐서 큰 다이아가 되는 관계식을 찾아야할 것 같은데 그걸 못찾겠음...

그래서 그냥 단순하게 부분합 + 브루트포스로 무작위 영역( sx, sy, ex, ey )의 합에서 안쪽 영역의 합  ( sx + 1, sy + 1, ex - 1, ey - 1 ) 을 뺀 값이 두 영역의 넓이의 차와 같은지 검사하는 방법으로 했다. 당연히 TLE 맞았다. ( O(N^4)... )

 

 이 상태로 홀딩하다 친구 과제 푸는데 그 문제 풀면서 나온 아이디어가 양방향에 대한 검사를 나눠서 한 쪽씩 진행하고 둘을 합산해 답을 찾는 것이었다.

이를 적용해 다이아몬드를 V 2개로 나누고 각 꼭짓점에서 양 날개 크기를 부분합으로 구한 뒤 반대 꼭짓점에서 만날 수 있는 크기의 반대 V를 찾는 아이디어를 떠올렸다.

이 알고리즘도 O(N^3) 이긴 하지만 상수가 작다. 위에 써놓은 것 처럼 짝수행 혹은 홀수행만 검사하기 때문에 750^2 * 375 이다. 한 2*10^8 정도 나온다.그리고 가장 큰 경우부터 내림차순으로 계산하며 다이아몬드를 찾은 경우 그 위치에서는 추가 검사를 할 필요가 없으므로 실제 계산량은 더 적다.

 

풀이 쓰고 보니까 문제가 쉬워보이는데 비숍 대각선 기믹에 매몰돼서 시간을 너무 버렸다.

---

코드::

/*
* 이게 왜 DP 임 ?
* 이게 DP 면 이 세상에 있는 모든 부분합 문제들은 다 DP 지
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct di {
	int y, d, p;
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m; vector<vector<int>> arr(n + 1, vector<int>(m + 1)); vector<vector<di>> ps1(n + 2, vector<di>(m + 2)), ps2(n + 2, vector<di>(m + 2));
	for (int i = 1; i <= n; i++) {
		string t; cin >> t;
		for (int j = 1; j <= m; j++) {
			arr[i][j] = t[j - 1] - 48;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] == 1) {
				ps1[i][j].y = ps1[i - 1][j - 1].y + 1; 
				ps1[i][j].d = ps1[i - 1][j + 1].d + 1;				
				ps1[i][j].p = ps1[i][j].y < ps1[i][j].d ? ps1[i][j].y : ps1[i][j].d;
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] == 1) {
				ps2[i][j].y = ps2[i + 1][j - 1].y + 1;
				ps2[i][j].d = ps2[i + 1][j + 1].d + 1;
				ps2[i][j].p = ps2[i][j].y < ps2[i][j].d ? ps2[i][j].y : ps2[i][j].d;
			}
		}
	}	
	int mx = 0;
	for (int j = 1; j <= m; j++) {
		for (int i = n; i >= 1; i--) {
			if (ps1[i][j].p > 0) {
				int p2p = i - ps1[i][j].p * 2 + 2;
				int base = i % 2 == 1 ? 1 : 2;
				int p2c = p2p > base ? p2p : base;
				while (p2c <= i) {
					if (((i - p2c) / 2 + 1) <= ps2[p2c][j].p) {
						mx = mx > ((i - p2c) / 2 + 1) ? mx : ((i - p2c) / 2 + 1);
						break;
					}
					p2c += 2;
				}
			}					
		}
	}
	cout << mx;
	return 0;
}