BOJ 1915 가장 큰 정사각형

 

문제 링크 : https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

 

각각의 i, j 에서 변의 길이 \( l \) 을 이용하여 loop 를 돌리면 시간 복잡도는 \( O(n^4) \) 이 된다.

2차원 부분합을 미리 구했다면  \(O(n^3)\) 으로 해결할 수 있지만 시간 초과일 것이다.

 

앞 단계에서 최대 정사각형을 찾기 위해 조사한 것을 재활용할 수 있음을 깨닫게 되면 DP 풀이는 쉽다.

 

우선 문자열 2차원 배열을 정수 2차원 배열 grid 에  저장했다고 가정한다. 

그리고, dp[i][j] 를 i , j 가 정사각형의 우측하단이 되는 최대의 정사각형의 값 k>0 라 하자.

(이때, grid[i][j]==1 일 것이다.)

그렇다면 dp[i-1][j-1] 은 k-1 이어야 할 것이고 dp[ i-1][j] , dp[i][j-1] 은 k-1 이상일 것이다.

이를 정리하면  grid[i][j]==1 일 때, 다음의 점화식이 성립한다.

 

dp[i][j] = 1 + min( dp[i-1][j-1] , dp[i-1][j], dp[i][j-1] )

 

이제는 루틴이다.

 

#include<bits/stdc++.h>

using namespace std;

int n,m,grid[1001][1001],dp[1001][1001];
char str[1001][1001];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",str[i]);
        for(int j=0;j<m;j++){
            int x=str[i][j]-'0';
            grid[i+1][j+1]=dp[i+1][j+1]=x;
        }
    }
    
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!grid[i][j])continue;
            dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
            ans=max(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans*ans);
}

 

 

최소값을 관리하는 2차원 세그먼트 트리를 사용하면 \( O(n^2 \log^2(n))\) 으로 해결할 수 있지만 생략한다.