백준 1915 가장 큰 정사각형 혼내주기

 

스코페 3번 문제와 유사한데 크기가 1000이다. 무식하게 풀면 시간 초과에 걸린다.
주어진 위치에서 가장 큰 정사각형의 한 변 길이를 저장하는 dp table을 만들면 된다. 아래의 그림에서 파랑색 점의 현재 위치를 [x][y]라고 할 때, [x-1][y-1], [x-1][y], [x][y-1]의 최솟값 + 1이 [x][y]의 값이 된다.

만약 이 문제가 스코페에 나왔다면 풀지 못했을 것 같다... 갈 길이 멀다.....

 

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

int map[1001][1001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> s;
        for(int j = 1; j <= m; ++j){
            map[i][j] = s[j-1] - '0';
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!map[i][j]) continue;
            map[i][j] = min({map[i-1][j-1], map[i-1][j], map[i][j-1]}) + 1;
            ans = max(ans, map[i][j]);
        }
    }
    cout << ans*ans;
}