[BOJ] 14925. 목장 건설하기

목장 건설하기

클릭시 이동합니다.

어떻게 풀까!?

이 문제는 DP 알고리즘 입니다!

정사각형이 어떻게 만들어지는지 알면 점화식을 통해 구할 수 있는 문제이죠!

3x3 에서 정사각형은 어떻게 만들어 질까요??

(i, j)에 3x3의 사각형을 만들 수 있는 경우를 살펴보겠습니다!

3x3 정사각형을 만들 수 있다면, (i, j-1) 에는 2x2의 정사각형을 만들 수 있습니다!

마찬가지로, (i-1, j)에도 2x2의 정사각형을 만들 수 있죠!

그리고! (i-1, j-1)에도 2x2 정사각형을 만들 수 있습니다!

반대로, (i-1, j-1)과 (i-1, j), (i, j-1)에 2x2 정사각형을 만들 수 있다면, (i, j)에는 3x3의 정사각형을 만들 수 있다는 것을 알 수 있습니다!

그럼, 다른 경우를 봅시다!

이런, 이번에는 왼쪽 위에 장애물이 있군요! 이 경우에는 어떻게 될까요??

(i-1, j-1)에는 1x1의 정사각형밖에 만들 수 없습니다!

(i-1, j)는 처음과 같이 2x2의 정사각형을 만들 수 있군요!

(i, j-1)도 마찬가지 입니다.

이렇게 알 수 있는 것은! (i-1, j-1), (i-1, j), (i, j-1) 중에서 가장 작은 값이 (i, j)에 만들 수 있는 사각형의 크기를 결정한다는 것 입니다!

따라서, 점화식은

가 됩니다!

이를 이용하면, 위의 그림에서는(i, j)에  1x1의 정사각형을 만들 수 있다는 것을 알 수 있습니다!

만약, (i, j)에 장애물이 있다면 0을 넣어주고 다음 칸을 살펴보도록 합시다.

코드

//https://www.acmicpc.net/problem/14925
#pragma once
#include<cstdio>
int map[1001][1001];
 
int min(int i1, int i2, int i3) {
    int res = i1 < i2 ? i1 : i2;
    res = res < i3 ? res : i3;
    return res;
}
 
int main() {
    int m, n;
    scanf("%d %d\n", &m, &n);
    int M = 0;
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int in;
            scanf("%d \n", &in);
            if (in == 0) {
                map[i][j] = 1;
 
                map[i][j] = min(map[i - 1][j - 1], map[i - 1][j], map[i][j - 1]) + 1;
                M = M > map[i][j] ? M : map[i][j];
            }
 
        }
    }
    printf("%d\n", M);
 
    return 0;
}

여담

SDS 알고리즘 특강에서 풀었던 문제입니다! 덕분에 즐겁게 쉽게 풀 수 있었습니다!

시간 복잡도는 이라는 것을 바로 알 수 있겠죠!