[BOJ] 14925 - 목장 건설하기 (Python)

 

 

아이디어

 

1915번 가장 큰 직사각형 문제와 유사한 문제로, 동적 계획법으로 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    M, N = map(int, input().split())
    board = [tuple(map(int, input().split())) for _ in range(M)]
    dp = [[0]*(N+1) for _ in range(M+1)]
    L = 0
    for i in range(M):
        temp = 0
        for j in range(N):
            if board[i][j] == 0:
                dp[i+1][j+1] = dp[i][j+1]+1
                if dp[i+1][j+1] > L:
                    temp += 1
                    if temp > L:
                        L += 1
                        temp = 0
                else:
                    temp = 0
            else:
                temp = 0
    print(L)

solution()