[백준 14925] 목장 건설하기 (C++)

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

14925번: 목장 건설하기

1. 주의할 점

- DP를 통해 해결한다

- 왼쪽, 위, 왼쪽위 대각선을 살핀다(처음엔 오랜쪽으로 했는데 바꿨다)

 

2. 구현

- 배열을 입력받을 때, 해당 배열의 원소가 0이면 해당 자리의 DP값을 왼쪽, 왼쪽위, 위와 비교하여 갱신한다

- 갱신된 DP값과 Maxi값을 비교하여 큰값을 Maxi에 할당한다

- Maxi를 출력한다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][1001];
int check[1001][1001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int row, col, maxi = 0;
	cin >> row >> col;
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++) {
			cin >> arr[i][j];
			check[i][j] = 0;
			if (arr[i][j] == 0) {
				int tt = MAX;
				tt = min(tt, check[i - 1][j]);
				tt = min(tt, check[i][j - 1]);
				tt = min(tt, check[i - 1][j - 1]);
				if (tt == MAX) tt = 0;
				check[i][j] = tt + 1;
				maxi = max(maxi, tt + 1);
			}
		}
	cout << maxi;
	system("pause");
	return 0;
}