[DP] 백준 1915 가장 큰 정사각형 만들기

참고한 블로그

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220800582008&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

그림을 보니까 이해가 됐다. 

입력받은 양의 공간만 사용해서 dp를 한게 아니라 필요에 따라 좀더 늘려서 할 수 있다는 걸 보여준 문제

ex. i,j == 1부터 입력받고 탐색은 i-1로 0부터 탐색한다. ==> 여기엔 자동으로 값이 0이 저장된 걸 이용

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <limits.h>

#include <queue>

#include <stack>

int min3(int a,int b,int c){

       a = (a < b ? a : b);

       return (a < c ? a : c);

}

using namespace std;

int tb1[100001];

int tb2[1001][1001];

int che[100001];

int che2[1001][1001];

bool doo[100001];

int n, m;

int main(void)

{

       cin >> n >> m;

       for (int i = 1; i <= n; ++i) {

              for (int j = 1; j <= m; ++j) {

                     scanf_s("%1d", &tb2[i][j]);

              }

       }

       int ans = 0;

       for (int i = 1; i <= n; ++i) {

              for (int j = 1; j <= m; ++j) {

                     if (tb2[i][j] == 1) {

                           che2[i][j] = min3(che2[i - 1][j - 1], che2[i - 1][j], che2[i][j - 1]) + 1;

                           ans = (ans < che2[i][j] ? che2[i][j] : ans);

                     }

              }

       }

       cout << ans*ans << endl;

       

       return 0;

}