[dynamic programing] 그릴 수 있는 최대 사각형 수 구하기

https://leetcode.com/problems/count-square-submatrices-with-all-ones/submissions/1282854201/

 

 

결국 정사각형의 크기가 얼마나되는지에 대한 정보는 한 cell에만 저장되면 된다.

[1, 1]

[1, 1] 이라면 이 정사각형의 크기는 2인데, 이를 기록하는 것은 한 번 이다.

 

그런데 그 크기 정보를 가장 오른쪽, 아래 모서리에 표시하게 된다면,

[1, 1]

[1, 2] 이렇게 표시가 되는것이고 이들을 다 더한 값인 5는 length=1인 정사각형 4개, length=2인 정사각형 1개의 의미와 동일해진다.

 

[1, 1, 1]       [1,1,1]

[1, 1, 1]       [1,2,2]

[1, 1, 1]  -> [1,2,3] 이런식으로.. 

 

즉, [a, b]

      [c, d] 일때, d값은 a,b 그리고 c가 모두 1일때만 하나 더 커진다.

 

위 논리로 모든 정사각형의 개수를 결국 그래프의 크기만큼의 시간복잡도로 구할 수 있고 O(m*n) = 300 * 300 = 90,000

한 값이 이전의 값들로 인해 결정된다 ---> dp

 

어떤 순서로 그래프를 탐색해야, 이전 값들의 값이 반영된 상태에서 값을 제대로 구할 수 있을까라는 쓸데없는 고민을 했다.

결국 세로, 가로에 대해 순차적으로 값을 넣으면 (이중 for문으로), graph[a][b]의 값을 넣을때 이미 a와 b보다 값이 작은 cell들은 모두 제 값이 반영된다.

 

위 고민때문에 머리 아파서 결국 gpt를 사용했는데,

쳐보고나서 바로 후회했다... 조금만 더 생각하면 스스로 풀 수 있는데 ㅠㅠ

from typing import List

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        max_length = max(len(matrix), len(matrix[0]))

        max_square = [[0]*len(matrix[0]) for _ in range(len(matrix))]
        total_square  = 0

        for j in range(len(matrix)):
            for i in range(len(matrix[0])):
                if matrix[j][i] == 1:
                    if j == 0 or i == 0:
                        max_square[j][i] = 1
                    else:
                        max_square[j][i] = 1
                        max_square[j][i] += min(max_square[j-1][i], max_square[j][i-1], max_square[j-1][i-1])
                    total_square += max_square[j][i]
        return total_square