[C/C++ 백준 1915번] 가장 큰 정사각형 (Gold 5)

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

1915번: 가장 큰 정사각형

예전에는 그렇게 생각 안나던 문제였는데, 다시보니 쉽게 풀린다.

DP라는 카테고리에 해당한다는 것을 알고보니 문제의 난이도가 훨씬 쉬워지는거 같기도 하다.

 

x, y를 오른쪽 끝으로 하는 정사각형의 가장 큰 변의 길이를 dp로 설정하자. 이때 x-1, y-1 / x-1, y / x, y-1 세 dp값에 의해 새로운 정사각형의 dp값이 결정된다. x, y가 0이라면 그냥 0, 아니라면 위 세 dp값 중 min값에 1을 더한 값이 길이이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[1001][1001]={};
int block[1001][1001]={};
int main(void){
	int n, m, maxi = 0;
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%1d", &block[i][j]);
			if(i==0 || j==0){
				if(block[i][j]==0)
					dp[i][j]=0;
				else
					dp[i][j]=1;
			}
			else if(block[i][j]==0)
				dp[i][j]=0;
			else{
				dp[i][j] += 1;
				dp[i][j] += min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
			}
			maxi = max(maxi, dp[i][j]);
		}
	}
	printf("%d", maxi*maxi);
}