개발공부/algorithm
[백준][python] 1915.가장큰정사각형 - DP
so.py
2021. 3. 27. 23:25
- 백준 1915 가장 큰 정사각형 Gold V
- python
- 문제링크
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
풀이
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)