https://www.acmicpc.net/problem/1915
시간 2초, 메모리 128MB
input :
- n, m(1 ≤ n, m ≤ 1,000)
- n개의 줄에는 m개의 숫자로 배열
output :
- 가장 큰 정사각형의 넓이를 출력
조건 :
- 1로 된 가장 큰 정사각형의 크기
첫 시작 부터 잘못 되었다. 각 자리에서의 누적합을 통해서 존재하는지를 확인하려 했는데. 헷갈려서. 실패 ㅋㅋㅋㅋㅋㅋㅋ
풀고 나서 지금 보니 가능은 할 것 같다. 근데 이렇게 구할 경우에 정사각형의 변의 길이를 지정하고, 나머지 dp로 계산을 해서 가지고 있는 모든 (1의 합 == 변 ** 2) 이 되어야 하기에
3중 for문을 써야하는데 시간복잡도가 터질거 같다.
그래서 다른 방법.
가지고있는 1의 합이 아닌, 각 위치에서 만들수 있는 정사각형 변의 최대길이를 저장하게 하는 것이다.
예를 들어.
3 4
1 1 1 1
0 1 1 1
1 1 1 1
이 있을 때.
1 1 1 1
0 1 2 2
1 1 2 3
이렇게 정사각형이 만들어질 수 있다. 각 자리의 값은 해당 자리에서 만들수 있는 정사각형의 길이이다.
어떤 자리(i, j)가 1일 때, 자기 왼쪽(i, j - 1), 대각선 위(i - 1, j - 1), 위(i - 1, j) 이 세 지점의 값 중 가장 작은 값 + 1 한 것이 새로 만들어 질 수 있는 정사각형의 길이인것이다.
0 1
1 1 이럴 때는 대각선 위가 없어서 정사각형을 늘릴 수 없다. 고로 자기자신만 따져서 1짜리 정사각형을 만든다.
1 1
1 1 이럴 때는 모든 점들이 정사각형을 이루고 있으니까
1 1
1 2 로 바뀌게 되고 정사각형의 길이가 2가 되는 것이다.
그러니까, 1 하나만 존재하는 것도 정사각형이기에 이도 따져줘야 한다.
min(data[i - 1][j], data[i - 1][j - 1], data[i][j - 1]) + 1이런 식을 이용하는 것인데, 맨 처음 입력 받을 떄 data 로 1 아니면 0을 입력 받으니까 그대로
data[i][j] += min(data[i - 1][j], data[i - 1][j - 1], data[i][j - 1])이렇게 작성해서 사용할 수 있다.
import sys
n, m = map(int, sys.stdin.readline().split())
data = [[0] * (m + 1)]
for i in range(n):
data.append([0] + list(map(int, sys.stdin.readline().rstrip())))
ans = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if data[i][j] == 1:
data[i][j] += min(data[i - 1][j], data[i - 1][j - 1], data[i][j - 1])
ans = max(ans, data[i][j])
print(ans ** 2)
