[백준] 4095 - 최대 정사각형

말 그대로 최대 정사각형의 크기를 구하는 문제

주어진 map에서 최대로 정사각형이 되는 크기의 너비나 높이를 구하면 됨

1. map을 순회하면서 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]의 최소 값을 구한다

 - 이유는 저 3개의 포인트는 각각 정사각형의 크기를 가진 값을 저장하기 때문

 - 하나라도 작으면 작은 사이즈의 정사각형을 넣어 주어야 하기 때문이다.

ex) 0 1 1 0 0                      0 1 1 0 0 

     0 1 1 1 0    ----->>>>>  0 1 4 1 0

     0 1 1 1 0                      0 1 4 4 0

     0 1 1 1 0                      0 1 4 9 0

2. 최소값의 너비나 높이를 구하기 위해 sqrt해주고, +1해 준 뒤 다시 제곱하여 dp[i][j]에 넣어준다.

3. 시간 복잡도는 O(N^2)이 된다.

#include <iostream>
#include <cmath>
#define MAXSIZE 1002
#define MIN(X, Y) ((X) > (Y) ? (Y) : (X))
using namespace std;
 
int map[MAXSIZE][MAXSIZE] = { 0 };
long long dp[MAXSIZE][MAXSIZE] = { 0 };
 
int main(void) {
    while (1) {
        int N, M, dab = 0;
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) {
                cin >> map[i][j];
                dp[i][j] = 0;
            }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1) {
                    long long size = MIN(dp[i - 1][j - 1], MIN(dp[i][j - 1], dp[i - 1][j]));
                    if (!size) dp[i][j] = 1;
                    else {
                        size = sqrt(size) + 1;
                        dp[i][j] = size * size;
                    }
                }
                else dp[i][j] = 0;
                dab = dab > dp[i][j] ? dab : dp[i][j];
            }
        }
        cout << sqrt(dab) << endl;
    }
    return 0;
}