같은 크기의 matrix 에 0, 0 부터 현재 index 까지 만들어지는 사각형 sum 을 저장하는 방식이 쉬우면서도 효율적인 접근이다. 왜인지 모르겠으나 불필요한 operation 이 포함된다고 생각해서 나는 같은 크기의 matrix 에 같은 row 에 있는 현재까지의 column sum 을 저장했다. 결론적으로 첫번째 접근보다 비효율적이다. 긴 row 에는 dp 에 여러번 접근해야할뿐더러 row 가 길수록 col1 을 빼주는 operation 을 많이 하게 된다.
class NumMatrix:
mat = None
def __init__(self, matrix: list[list[int]]):
self.mat = [[0] * len(matrix[0]) for _ in range(len(matrix))]
for r in range(len(matrix)):
self.mat[r][0] = matrix[r][0]
for c in range(1, len(matrix[0])):
self.mat[r][c] = self.mat[r][c - 1] + matrix[r][c]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
blk = 0
for r in range(row1, row2 + 1):
blk += self.mat[r][col2]
blk -= self.mat[r][col1 - 1] if col1 > 0 else 0
return blk