(C++) - 백준(BOJ) 1915번 : 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

dp문제였습니다.

풀이방법

 2 X 2짜리 정사각형을 생각합니다. 

i행 j열이 1이라면 이전에 가장 큰 정사각형의 한 변의 길이가 저장된 (i-1,j-1),  (i-1,j),  (i,j-1) 위치의 값들중 최소인값 + 1을 저장합니다. 점화식으로 나타낸다면

min({square[i-1][j-1],square[i-1][j],square[i][j-1]}) + 1

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, m, ans;
int square[1001][1001], d[1001][1001];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%1d", &square[i][j]);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(square[i][j]){
                square[i][j] = min({square[i-1][j-1],square[i-1][j],square[i][j-1]}) + 1;
                ans = max(ans,square[i][j]);
            }
        }
    }
    cout << ans * ans;
}