[BOJ 1915] 가장 큰 정사각형 (Python)

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

1915번: 가장 큰 정사각형

완전탐색으로 풀면 시간초과가 날 수 있는 문제.

DP를 이용하면 O(NM)으로 풀 수 있다.

핵심 점화식은

d[i][j] = min(d[i - 1][j - 1], d[i - 1][j], d[i][j - 1]) + 1

여기서 d[i][j]는 i행 j열을 오른쪽 끝으로 하는 정사각형 한변의 최대 길이이다.

최종적으로 d 배열에서 최댓값을 구하면 만들 수 있는 가장 큰 정사각형의 변의 길이가 나오고

제곱하여 답을 구할 수 있다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().rstrip())) for _ in range(n)]
d = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            if i >= 1 and j >= 1:
                d[i][j] = min(d[i - 1][j - 1], d[i - 1][j], d[i][j - 1]) + 1
            else:
                d[i][j] = 1

print(max(list(map(max, d))) ** 2)

DP는 아이디어를 생각해내는 것이 핵심인데,

경험에 의해 이 아이디어를 캐치하는 능력을 기를 수 있다고 생각한다. 

풀다보면 감각이 생길 것이다.

 

완전탐색으로 풀 수 있는 문제는

시간 초과가 우려될 경우 DP를 의심해봐야한다.

또한, 앞서 구한 부분문제의 답이 다른 문제의 답으로 이용되는 경우여야 한다.

 

점화식을 찾아낸다면 굉장히 간단하게 풀 수 있다.