[BOJ] 가장 큰 정사각형

가장 큰 정사각형

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ n, m ≤ 1,000)	Dynamic Programming

이것도 전형적인 dp 문제로 점화식이 굉장히 직관적이라 풀기 좋았습니다.. 요즘 어려운 문제 보다가 이런 문제 보니까 그나마 숨이 트이네요.. ㅠㅜ

현재 위치에서 정사각형이려면 위에서 정사각형이였던 애들을 전부다 검사해서 왼쪽, 위, 좌 대각선에 있는 값이 전부다 정사각형이었다면 그 중에서 작은 친구의 정사각형 값을 1 확장해주면 된다.

이런 아이디어로 AC를 맞았습니다. 근데 y <= && x <= 0 조건을 이따구로 써서 2번 틀렸는데 조심하셔요.. 무의식적으로 작성된 코드는 사람을 고뇌에 빠트립니다.

정답 코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

int n, m;
int dp[1001][1001];


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int current;
    char tmp;
    int result = 0;
    cin >> n >> m;
    for(int y = 0; y < n; y++){
        
        for(int x = 0; x < m; x++){
            cin >> tmp;
            
            current = tmp - '0';
            dp[y][x] = current;

            if(current){
                if(x <= 0 || y <= 0) continue;
                
                dp[y][x] = min({dp[y][x-1], dp[y-1][x], dp[y-1][x-1]}) + 1;
            }
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            result = max(result, dp[i][j]);
        }
    }
    cout << result * result;
    
    return 0;
}