Category
알고리즘  dp

[14925] 목장 건설하기

by Hwang

문제

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

풀이

board[i][j]는 (i, j) 위치를 정사각형의 가장 오른쪽 아래 지점이라 할 때 만들 수 있는 가장 큰 한 변의 길이를 의미한다.

여기서 대각선 dp[i-1][j-1]를 고려해줘야하는 이유는

[0, 0, 0]
[0, 1, 0]
[0, 0, 0]

위와 같은 상황에서 (2, 2)을 구해줄 때 위와 아래만 고려하면 2라는 크기가 나온다. 따라서 대각선 방향도 고려해야함

import sys

M, N = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
max_length = 0

for i in range(1, M+1):
    for j in range(1, N+1):
        if board[i-1][j-1] == 0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            max_length = max(dp[i][j], max_length)
print(max_length)


 Comment