[백준] 1915 가장 큰 정사각형

1915번: 가장 큰 정사각형

문제 확인

 

1000 x 1000 크기 이므로 완전 탐색으로 풀면 시간 초과가 나므로 dp로 풀어야 합니다.

 

풀이

 

dp 배열의 의미를 현재 위치에서 만들 수 있는 최대 크기의 정사각형으로 둡니다.

현재 위치(i, j)에서 만들 수 있는 가장 큰 정사각형은 (i-1, j), (i-1, j-1), (i, j-1)의 최솟값 + 1 이 됩니다.

그 이유는 (i-1, j-1)의 값이 뒷부분 정사각형을 채워주고 (i, j-1), (i-1, j) 값이 새로워 가로를 채워주는 역할을 하기 때문입니다.

다음의 경우 dp[i-1, j-1] = 3, dp[i-1, j] = 3, dp[i, j-1] = 2이며 dp[i, j]에서 만들 수 있는 최대 정사각형의 크기는 2+1 = 3이 됩니다.

 

따라서 현재 i 번째 가로 dp를 계산할 때 i-1이 필요하며 i-2 이전 배열은 필요가 없으므로 메모리 사용량을 줄이기 위해 dp[2][1001]을 사용하고 비트 반전을 이용해서 dp 배열을 채워줍니다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n, m;
    cin >> n >> m;
 
    short dp[2][1001] = { 0 }, mx=0;
    char ary[1001] = { 0 };
 
    for (int i = 1, f = 0, nf = 1; i <= n; i++) {
        cin >> ary;
        for (int j = 1; j <= m; j++) {
            if (ary[j - 1] != '0') {
                dp[f][j] = min({ dp[nf][j], dp[nf][j - 1], dp[f][j - 1] }) + 1;
                if (dp[f][j] > mx)
                    mx = dp[f][j];
            }
            else
                dp[f][j] = 0;
        }
        nf = !nf;
        f = !f;
    }
    cout << mx * mx;
}