[C++] 백준1915 - 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

DP 없이 풀다가 시간 초과..ㅋㅋ ㅠㅠ 

 

일단 사각형이 되기 위해서는 사각형 내부(테두리 포함) 모두 1이어야 한다.

 

DP를 이용하면, 해당 좌표( i, j )의 ↑ ↖ ← 세 방향의 값의 최소값에 1을 더해주면 된다.

만약 세 방향 중 하나라도 0이 있으면 값이 1이 되고, 1은 칸 1개짜리 정사각형이다.

 

ex) 세 방향의 값이 각각 2, 4, 5 인 경우 dp값은 3이 된다.

초록색 부분은 신경 안 써도 된다. 4랑 5 앞칸이 0이었다면 4랑 5칸에 1이 있었을 것임 ( 최소값 0 + 1 = 1 ) 

 

점화식

dp[i][j] = min( min(dp[i-1][j-1] , dp[i-1][j]) , dp[i][j-1])

 

[코드]

#include <iostream>
#include <vector>

using namespace std;

int map[1001][1001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	

	for (int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		
		for (int j = 0; j < m; j++) {
			map[i][j+1] = str.at(j) - '0';
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0)
				continue;

			map[i][j] = min(min( map[i - 1][j - 1], map[i - 1][j]), map[i][j - 1] ) + 1;

			ans = max(ans, map[i][j]);
		}
	}

	ans *= ans;
	cout << ans;
}