[BaekJoon] 1915번 : 가장 큰 정사각형

Updated:

1915번 : 가장 큰 정사각형


(1, 1) 부터 (n-1, m-1) 까지 이동하면서 DP 를 이용해 정사각형 개수를 세는 문제이다.

현재 위치를 기준으로 현재 위치, 왼쪽, 위쪽, 왼쪽 위 대각선의 값이 모두 0 보다 크면 정사각형이 되는 것을 알 수 있다.

정사각형이 되는 것은 알았으니 크기를 정할 차례인데 세 위치 중 가장 작은 값의 제곱근을 구한 뒤 1을 더해 제곱을 해주면 된다.

image


def solution():
	global arr
	up = [-1, 0]
	left = [0, -1]
	left_up = [-1, -1]

	for i in range(1, n):
		for j in range(1, m):
			up_val = arr[i + up[0]][j + up[1]]
			left_val = arr[i + left[0]][j + left[1]]
			left_up_val = arr[i + left_up[0]][j + left_up[1]]
			if 0 < up_val and 0 < left_val and 0 < left_up_val and 0 < arr[i][j]:
				arr[i][j] = (int(min(up_val, left_val, left_up_val) ** 0.5) + 1) ** 2

	return max(sum(arr, []))


if __name__ == '__main__':
	n, m = map(int, input().split())
	arr = [list(map(int, input())) for _ in range(n)]

	print(solution())



Categories:

Updated:

Leave a comment