[백준][python] 1915.가장큰정사각형 - DP

• 백준 1915 가장 큰 정사각형 Gold V
• python
• 문제링크

1915번: 가장 큰 정사각형

풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

s = [[0 for i in range(M + 1)]]

for i in range(n): s.append([0] + list(input().strip()))
dp = [[0] * (M + 1) for i in range(N + 1)]
res = 0

for i in range(N + 1):
    for j in range(M + 1):
        if s[i][j] == "1": dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])+ 1

for i in range(N + 1):
    for j in range(M + 1):
        res = max(result, dp[i][j])

print(res ** 2)