[백준] 11660번 구간 합 구하기 5

 

 

실패한 접근법

- matrix를 그리고 반복문을 통해 구현

→ 시간초과로 실패

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]

for _ in range(m):
    result = 0
    x1,y1, x2,y2 = map(int, input().split())
    
    for i in range(y1, y2+1):
        
        if x1 == x2 :
            result += matrix[i-1][x1-1]
        else:
            result += sum(matrix[i-1][x1-1:x2])
            
    print(result)

 

올바른 접근법

- 누적합 이용

- 누적합에 대한 dp를 구함

- 이전의 누적합을 활용하여 계산

dp[x][y] = dp[x-1][y] + dp[x][y-1] - dp[x-1][y-1] + matrix[x-1][y-1]

 

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(n+1) for _ in range(n+1)]
for x in range(1,n+1):
    for y in range(1,n+1):
        dp[x][y] = dp[x-1][y] + dp[x][y-1] - dp[x-1][y-1] + matrix[x-1][y-1]

for i in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    
    result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(result)