304. Range Sum Query 2D - Immutable(Medium)

 

Range Sum Query 2D - Immutable - LeetCode

 

이것도 DP문제라면 DP문제. 합을 누적해서 활용해야 하니깐.

가장 큰 사각형에서 row기준, col기준으로 각각 빼주고 중복뺀건 더해주면 된다.

 

class NumMatrix:
    matrix = list()
    matrix_sum = dict()
    def sumArr(self, row, col):
        sum = 0
        for i in range(row+1):
            sum += self.matrix_sum[i][col]
        return sum
    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        for row in range(len(matrix)):
            self.matrix_sum[row] = dict()
            sum = 0
            for col in range(len(matrix[row])):
                sum += matrix[row][col]
                self.matrix_sum[row][col] = sum
                # print("Matrix[{}][{}] = {} - Matrix_Sum[{}][{}] = {}".format(row,col,matrix[row][col],row,col,self.matrix_sum[row][col]))
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        result = self.sumArr(row2, col2)
        # print("sumArr[{}][{}] = {}".format(row2,col2,result))
        if row1 != 0:
            minus = self.sumArr(row1-1, col2)
            result -= minus
            # print("- sumArr[{}][{}] = {}".format(row1-1,col2,minus))
        if col1 != 0:
            minus = self.sumArr(row2, col1-1)
            result -= minus
            # print("- sumArr[{}][{}] = {}".format(row2,col1-1,minus))
        if row1 != 0 and col1 != 0:
            plus = self.sumArr(row1-1, col1-1)
            result += plus
            # print("- sumArr[{}][{}] = {}".format(row1-1,col1-1,plus))
        return result