[BAE/<JOON> 문제풀이] 14925. 목장 건설하기

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

14925번: 목장 건설하기

풀이::
목장 모양이 정확하게 정사각형이어야 하므로 DP[x][y] = 그 칸을 포함하며 좌상단으로 확장하는 정사각형 크기 중 MAX 으로 정의하면

dp[x - k][y - k] 값 들을 검사하다 이미 탐색된 값을 발견하면 해당 지점부터는 정사각형이 있는 것이 확정되므로 중복 계산하지 않을 수 있다.

맵으로 표현하면 다음과 같다. 

1110
1110
1110
0000

이렇게 생긴 맵에서 좌상단부터 검사를 시작하면 

1110
1220
1230
0000

이렇게 가장 큰 정사각형 크기를 구할 수 있는데 이 때, 우측 변과 하단 변만 검사하고 dp[x - 1][y - 1] 값만 검사하면

총 (x - 1) * (y - 1) 에 해당하는 이미 검사된 구역을 중복 검사하는 일을 피할 수 있다.

의견::
그냥 다이나믹 문제
꿀문제임. 솔직히 실제 난이도 실버 하윈데 골드4 문제임. 맛!있!다!

코드::

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1001][1001];
int dp[1001][1001];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] > 0) continue;
			int cnt = 1;
			for (int k = 1; k <= dp[i - 1][j - 1]; k++) {
				if (arr[i][j - k] > 0 || arr[i - k][j] > 0) {
					break;
				}				
				cnt++;
			}

			dp[i][j] = cnt;
			mx = cnt > mx ? cnt : mx;
		}
	}

	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}*/

	cout << mx;
	return 0;
}