3070. Count Submatrices with Top-Left Element and Sum Less Than k

 

사실 그렇게 어려운 문제는 아니었습니다.

 

weekly contest에서 두번째로 나왔던 문제로,

prefix sum을 사용해서, 각 row의 합을 저장해서 새로운 list에 저장하고,

새로운 row에서 iterate할 때는 새로운 row에서 그 row의 합들과 지금까지 더한 위의 row의 합을 더해주는 방식으로 해서 몇 번의 시행착오 끝에 풀어낼 수 있었습니다.

 

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid[0]), len(grid)
        new_matrix = [[0 for _ in range(m)] for _ in range(n)]
        # print(new_matrix)
        count = 0
        for j in range(n):
            row_sum = grid[j]
            for i in range(m):
                # new_matrix[j][i] = grid[j][i] 
                if j > 0:
                    new_matrix[j][i] += new_matrix[j-1][i]
                if i > 0:
                    row_sum[i] += row_sum[i-1]
                new_matrix[j][i] += row_sum[i]
                # if count?
                if new_matrix[j][i] <= k:
                    count += 1
                # print(new_matrix[j][i])
        # print(new_matrix)
        return count