[BOJ] 1915번 : 가장 큰 정사각형 (C++)

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

1915번: 가장 큰 정사각형

 

dp문제이므로 테이블 설정을 잘해줘야 한다. 

d[a][b]=k : (a,b)까지 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 k이다.

그러기 위해선 지금 좌표를 기준으로 위쪽, 왼쪽, 대각선왼쪽을 볼 필요가 있다. 

(a,b)를 기준으로 위의 세 군데 중에서 1이 아닌 0을 갖게 되면 지금 나의 좌표에서 만들 수 있는 정사각형의 크기가 다시 1로 초기화된다. 

그러니깐 현재 좌표를 기준으로 위,왼,대각선왼쪽에 영향을 받게 되는 것이다. 

그래서 나머지 두 좌표가 아무리 커도 최솟값에 의해 초기화되므로 min(위쪽, 왼쪽, 왼쪽대각선) 을 이용하여 문제를 풀어야 한다. 

 

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int n,m;
int board[1005][1005];
int d[1005][1005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(int i=1; i<=n; i++){
        string s;
        cin>>s;
        for(int j=1; j<=m; j++){
            board[i][j] = s[j-1]-'0';
        }
    }

    int ans=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(board[i][j]){
                d[i][j]=min({d[i-1][j],d[i][j-1],d[i-1][j-1]})+1;
                ans = max(ans, d[i][j]);
            }
        }
    }

    cout<<ans*ans;
}