백준 목장 건설하기 14925

문제

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

해결방법

dp[i][j] = i, j일때 만들 수 있는 직사각형길이
자신의 왼쪽 왼위쪽 대각선 위쪽을 보면서 최솟 값 + 1을 해주면 현재에서 만들 수 있는 최대 길이가 나온다

1. 이문제에서 틀릴 수 있는 점 초기 ans를 생각없이 -1f로 두었는데 그때 문제는 모든 목장에 1이나 2가 도배 되었을 경우 출력이 0이 아니라 -1로 되어서 틀릴 수 있다.

2. 이것을 top down으로 할려고하는데 틀렸다 어디가 문제였지?....

3. 처음에 dp인데 어떻게 접근할지 생각을 못해서 다른분의 블로그를 참고하였다 출처 : https://sangdo913.tistory.com/116 님 감사합니다

소스

#include <bits/stdc++.h>

using namespace std;

int m, n, ans ;
int a[1001][1001];
int dp[1001][1001];
bool chache[1001][1001];
//dp[i][j] => i,j에서 만들 수 있는 정사각형의 크기 
// dp[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1;
// 

int main() {

    cin >> m >> n;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] == 0) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                ans = max(dp[i][j], ans);
            }
        }
    }
    cout << ans;
    return 0;
}