[BOJ/백준][Gold4] 14925 : 목장 건설하기 (C++)

 

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

14925번: 목장 건설하기

 

[난이도] Gold4
[유형] DP

[풀이]
DP를 이용해 O(N*M)에 해결이 가능합니다.
dp[i][j] : (i,j) 가 오른쪽 아래 모서이리 때 만들 수 있는 정사각형의 변의 최대 길이.
점화식을 위와 같이 정의했을 때, dp[i][j]가 최소 1이 되려면 map[i][j]==0 이어야 합니다.
이제 미리 구해져 있는 dp[i-1][j-1],dp[i][j-1],dp[i-1][j] 값들을 이용해 최대 길이를 구할 수 있습니다.
위 세 개의 값을 1개라도 0이면 1보다 큰 정사각형을 만들 수 없기 때문에 예외처리 해줍니다.

그 후엔 아래와 같은 점화식으로 세 값중 가장 작은 값에 1을 더한 값이 dp[i][j]가 됩니다.
dp[i][j]=min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;

그림을 그려보시면 쉽게 파악이 되실 겁니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int M,N,map[1001][1001],dp[1001][1001];
int main(){
    scanf("%d%d",&M,&N);
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    int ans=0;
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            if(!map[i][j]){
                if(!dp[i-1][j-1] || !dp[i][j-1]|| !dp[i-1][j]) dp[i][j]=1;
                else dp[i][j]=min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14925.cpp