백준 1028 / C++

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

1028번: 다이아몬드 광산

 

[ 풀이 ]

한 점 (i,j)에서 왼쪽아래, 오른쪽 아래 대각선으로 최대로 긴 연속된 1의 개수를 저장해놓자. 

다이아몬드의 비교는 한 점을 기준으로 min(왼쪽, 오른쪽)을 찾고 그 사이의 길이에 대해 탐색해주면 된다.

시간복잡도는 O(N^3/2)정도 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int n, m, a[777][777], dp[2][777][777];

int solve(int i, int j) {
	// 최대 길이
	int l = min(dp[0][i][j], dp[1][i][j]) - 1;
	if (l < 0) return 0;
	int ret = 1;
	// 그 길이보다 작은 모두 경우 탐색 
	for (int k = 1; k <= l; k++) {
		if (i + k > n || j + k > m || j - k < 1) continue;
		if (min(dp[1][i + k][j - k], dp[0][i + k][j + k]) >= k + 1) {
			ret = k + 1;
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char x; cin >> x;
			a[i][j] = x - '0';
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 1; j--) {
			if (a[i][j]) {
				// 왼쪽 대각선 
				dp[0][i][j] = dp[0][i + 1][j - 1] + 1;
				// 오른쪽 대각선 
				dp[1][i][j] = dp[1][i + 1][j + 1] + 1;
			}
			else {
				dp[0][i][j] = 0;
				dp[1][i][j] = 0;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = max(ans, solve(i, j));
		}
	}
	cout << ans;
}