[DP] BOJ 1915 가장 큰 정사각형 (C++)

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

문제 해결 알고리즘

 

다이나믹 프로그래밍으로 주변에 있는 사각형들 중 가장 작은 크기의 정사각형 크기에서 + 1 해준다.

갱신해줄 때마다 최댓값도 갱신해준다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int n, m, result = 0;
int dp[1001][1001];

void find_max_square(){

    for(int k=1;k<min(n,m);k++){
        for(int i=0;i<n-k;i++){
            for(int j=0;j<m-k;j++){
                
                if(dp[i][j]) {
                    dp[i][j] = min(dp[i+1][j], min(dp[i+1][j+1], dp[i][j+1])) + 1;


                    result = max(result, dp[i][j]);
                }

            }
        }
    }
}

int main(){
    cin >> n >> m;

    for(int i=0;i<n;i++){
        string str; cin >> str;
        for(int j=0;j<str.size();j++){
            dp[i][j] = str[j] - '0';

            if(dp[i][j] == 1) result = 1;
        }
    }

    find_max_square();

    cout << result * result;

}