다이나믹 프로그래밍
- 작은 문제의 답이 큰 문제의 답을 계산할 때 활용
- 두 가지 풀이 방법이 있음
- 상향식 풀이: for 문 돌면서 작은 문제부터 답을 계산
- 하향식 풀이: 분할정복 형태로 문제를 쪼개면서 재귀로 구현
- 점화식을 세울 때
- 작은 문제의 답부터 생각해볼것
- 큰 문제의 답을 작은 문제 답으로 계산할 수 있는지 생각해볼것
- 메모이제이션
- 초기값 설정을 잘 해야 함 (메모리를 한칸 더 크게 잡는다던가)
풀이
1) 숫자 1이 적혀있으면 너비가 1인 정사각형이다.
2) (i,j)를 오른쪽 아래 모서리로 잡고 정사각형을 만들때
3) dp에 저장하는 값은 정사각형 한변의 길이
4) dp(i,j) = min(dp(i-1,j-1), dp(i-1,j), dp(i,j-1)) + 1
5) 즉, 앞서 구한 정사각형 변 길이의 최소값 + 1 을 하면 지금 만들 수 있는 최대 크기의 정사각형의 한 변 길이가 나온다.
"""
DP
"""
import sys
def solve(data, mem):
"""
mem[i][j] = min(min(mem[i-1][j], mem[i][j-1]), mem[i-1][j-1]) + 1
:return:
"""
max_w = 0
for i in range(1, n+1):
for j in range(1, m+1):
if data[i-1][j-1] == 1:
mem[i][j] = min(mem[i - 1][j], mem[i][j - 1], mem[i - 1][j - 1]) + 1
if mem[i][j] > max_w:
max_w = mem[i][j]
return max_w
sys.stdin = open('./1915.txt')
n, m = list(map(int, input().split()))
mem = [[0 for _ in range(m+1)] for _ in range(n+1)] # dummy 메모리를 한줄씩 추가한다
data = []
for i in range(n):
line = input()
line = [int(d) for d in line]
data.append(line)
out = solve(data, mem)
print(out*out)
