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

문제 :

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

분석 :

대표적인 DP 문제로 1씩 더하는게 곧 정사각형의 한 변이 된다는 게 신기했다. DP가 전에 한번 공부했을 때 잘 이해가 안됐는데 이번에 조금 알거 같다는 생각이 들었다. 우선 arr이라는 원래 2차원 배열을 만들고 memo라는 배열에 값을 계산해 누적한다.

arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 모두가 1일때만이 arr[i][j]과 함께 정사각형을 만들 수 있으므로 그런 경우만 검사 한 뒤 1을 더해 한변을 memo 배열에 누적해 놓고 ans에 값을 갱신하여 정사각형의 넓이를 계산한다. 

 

c++ 코드 :

//
//  1915_square.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/05.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int R1, R2;
int arr[1001][1001] = {0};
int memo[1001][1001] = {0};
string s;
int ans = 0;



void input(){
    cin >> R1 >> R2;
    for(int i = 0; i < R1; i++){
        cin >> s;
        for(int j = 0; j < R2; j++){
            arr[i][j] = s[j] - 48;
            if(arr[i][j] == 1){
                memo[i][j] = 1;
                ans = memo[i][j];
            }
        }
    }
}

void find_biggest_square(){
    for(int i = 1; i < R1; i++){
        for(int j = 1; j < R2; j++){
            if(arr[i-1][j-1] == 1 && arr[i-1][j] == 1 && arr[i][j-1] == 1){
                memo[i][j] = min(memo[i-1][j-1], memo[i-1][j]);
                memo[i][j] = min(memo[i][j], memo[i][j-1]) + 1;
            }
            ans = max(ans, memo[i][j]);
        }
    }
    cout << ans * ans << endl;
    
    
    
}

int main (){
    input();
    find_biggest_square();
    return 0;
}