[14925번] 목장 건설하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

http://www.crocus.co.kr/826

위 링크와 코드가 같고(arr[i][j]가 !arr[i][j]만 다릅니다.) 설명을 적어두었기에 위의 링크를 참조하시면 됩니다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int DP[1003][1003];
int arr[1003][1003];
int ans;
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &arr[i][j]);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!arr[i][j])
            {
                DP[i][j] = min({ DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1] }) + 1;
                ans = max(DP[i][j], ans);
            }
 
    cout << ans;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>