취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14925번 문제인 목장 건설하기이다.
문제는 아래 링크를 확인하자.

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

dp[r][c]를 "r행 c열을 가장 오른쪽 아래 칸으로 갖는 가장 큰 정사각형의 한 변의 길이"로 하면 해당 칸이 빈 칸인 경우 다음과 같은 식이 성립합을 관찰할 수 있다.

dp[r][c] = min(dp[r-1][c-1], dp[r-1][c], dp[r][c-1]) + 1

빈 종이등에 정사각형들을 직접 그려보면 위 식의 이해가 쉬울 것이다.

물론 해당 칸에 나무나 바위가 있다면 dp[r][c] = 0이 된다.

위의 점화식과 메모이제이션을 이용하여 문제를 빠르게 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C;
int ans = 0;
int dp[1001][1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			int x; cin >> x;
			if (x > 0) continue;
			int tmp = min(dp[r - 1][c - 1], min(dp[r - 1][c], dp[r][c - 1])) + 1;
			dp[r][c] = tmp;
			ans = max(ans, tmp);
		}
	}

	cout << ans;
}