[백준 1915 가장 큰 정사각형 문제] PYTHON

 

전형적인 Dynamic Programming 문제로 머리를 굴려서 방안을 모색해야 한다.

새로운 DP 배열을 사용하기보다 주어진 배열을 사용하기로 했다.

문제를 푸는 법은 기존의 배열에서 for 문으로 모든 index를 탐색하며

만약 자신, 왼쪽, 위, 왼쪽 위의 index 값이 1일 경우 정사각형을 이루므로

자신을 제외한 3개의 index의 min 값을 자신의 index에 더하는 것으로 구현했다.

만약 길이 3짜리 정사각형일 경우 왼쪽, 위, 왼쪽 위의 min 값은 2가 되므로 길이 3이상에서도 문제없다.

 

DP문제는 구현은 비교적 쉬운 것 같지만 상상을 많이 해야해서 힘든 것 같다.

 

case = []
N, M = map(int, input().split())
for _ in range(N):
    case.append(list(map(int, input().rstrip())))
answer = 0

for i in range(0, N):
    for j in range(0, M):
        if i > 0 and j > 0 and case[i][j] != 0:
            case[i][j] += min(case[i-1][j-1], case[i][j-1], case[i-1][j])
        answer = max(answer, case[i][j])

print(answer*answer)