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

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제 입력 1

4 4 0100 0111 1110 0010

예제 출력 1

4

 

---

 

 내 소스

 

#include <iostream>

using namespace std;

int main(){
    int n;
    int m;
    int i;
    int j;
    int min;
    int answer = 0;
    
    int **arr;
    int **dp;
    
    char c;
    
    cin >> n;
    cin >> m;
    
    arr = new int*[n];
    dp = new int*[n];
    
    for(i=0; i<n; i++){
        dp[i] = new int[m];
        arr[i] = new int[m];
        for(j=0; j<m; j++){
            cin >> c;
            arr[i][j] = c - '0';
            dp[i][j] = 0;
        }
    }
    
    for(j=0; j<m; j++){
        dp[0][j] = arr[0][j];
    }
    
    for(i=0; i<n; i++){
        dp[i][0] = arr[i][0];
    }
    
    for(i=1; i<n; i++){
        for(j=1; j<m; j++){
            if(arr[i][j]==1){
                min = dp[i-1][j-1];
                if(dp[i-1][j] < min){
                    min = dp[i-1][j];
                }
                if(dp[i][j-1] < min){
                    min = dp[i][j-1];
                }
                dp[i][j] = min + 1;
            }
        }
    }
    
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            if(dp[i][j] > answer){
                answer = dp[i][j];
            }
        }
    }
    cout << answer * answer;
    
    return 0;
}