11660번 - 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

이 문제는 저번에 풀었던 일차원 배열의 누적합을 구하는 문제인 '구간 합 구하기 4'에서 배열의 차원을 이차원으로 늘린 것이다. 일차원 배열일 때는 단순히 생각할 수 있었는데, 이차원으로 확장하니 무엇을 빼고 더해야 하는지 개념이 잘 안 잡혔다.

책을 펼쳐서 누적합의 개념에 대해 살펴보았다.

sum(y1, x1, y2, x2) = psum[y2][x2] - psum[y2][x1-1] - psum[y1-1][x2] + psum[y1-1][x1-1]

이 식을 통해서 구할 수 있다. 중복되는 부분은 제거하고, 모두에게 포함되는 psum[y1-1][x1-1]은 두 번 빼졌기 때문에 한 번 더해주는 것이다. 이 개념이 잡히고 나니 문제를 푸는데 필요한 수식을 세우는 것은 쉬웠다. 

 

# 구간 합 구하기 5
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp[1][1] = arr[0][0]
for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i-1][j-1]

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