백준 14925 : 목장 건설하기

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

14925번: 목장 건설하기

1. 왜 DP Matrix와 Board 의 크기는 다른가?

 어찌저찌 점화식을 만들고 문제를 풀었다고 생각했는데, 계속해서 틀리길래 다른 분들이 해둔 것을 참고했다. 내가 틀린 부분은 방문함수와 입력받은 보드판의 크기를 갖게 해서 였다. 왜 그런가... 계속 생각해봤다... 생각해보니 DP좌표계에서는 보드판의 시작포인트(0, 0) 정보 또한 업데이트 해주어야 한다는 점을 놓치고 있었다. 그림으로 그려보면,

위와 같이 된다. 한마디로, 예를 들어 (0, 0)인 포인트에서 사각형의 개수를 판단할때에는 그 위의 가상의 공간을 만들어서 초기조건을 부여해주어야 정답처리가 가능한 것이다... 어렵다.. DP. 제일 짧으면서도 이해가 잘안된다... 큰일..

2. 전체 코드

메모리 : 132832 KB, 시간 : 232 ms, 풀이시간 : 180 min + a

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

def solve():
    maxValue = 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
                maxValue = max(maxValue, dp[i][j])
    return maxValue

print(solve())