Today's Challenge

https://leetcode.com/problems/range-sum-query-2d-immutable/

Range Sum Query 2D - Immutable - LeetCode

오늘은 오랜만에 Medium 등급의 문제가 나왔다.
생각보다 어려웠다. 2D 누적합 문제였는데, 단순 for문으로 풀었더니 TL이 발생해서 DP로 수정했다.

# TL 발생 코드
class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for y in range(row1, row2+1):
            for x in range(col1, col2+1):
                res += self.matrix[y][x]                
        return res

# PASS한 코드
class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.dp=[[0] * (len(matrix[0])+1) for _ in range(len(matrix)+1)]        
		
        for r in range(len(self.dp)-1):
            for c in range(len(self.dp[0])-1):
                self.dp[r+1][c+1]=matrix[r][c] + self.dp[r][c+1] + self.dp[r+1][c] - self.dp[r][c]
        
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]