가장 큰 정사각형

• DP의 규칙을 찾아내는 과정이 어렵다
• 규칙을 생각해내면 허무한 문제

import sys

n, m = map(int,sys.stdin.readline().split())

arr = []

for i in range(n):
    arr.append(sys.stdin.readline())

re = [[0 for i in range(m)] for j in range(n)]

max_num = 0

for i in range(n):
    for j in range(m):
        if arr[i][j] == '0':
            # 0일 때는 제외
            continue
        if i - 1 < 0 or j - 1 < 0:
            # 왼쪽과 윗면에 접하면 1값을 준다
            re[i][j] = 1
            max_num = max(re[i][j], max_num) 
        else:
            # 위, 왼쪽, 위왼쪽대각선만 확인한다
            # 계속해서 갱신된 값들의 min값에 1을 더해준다
            re[i][j] = min(re[i-1][j-1], re[i-1][j], re[i][j-1])+1
            max_num = max(re[i][j], max_num)

print(max_num**2)

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제 입력 1

4 4
0100
0111
1110
0010

예제 출력 1

4