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

 

 

문제

---

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

11660번: 구간 합 구하기 5

 

 

나의 풀이

---

dp를 사용하면 된다.

dp 2차원 리스트에 각 위치에는 (0,0)부터의 부분합을 저장한다.

주황색 부분의 부분합을 구하려면 전체 합에서 A, B, C 부분을 빼주면 된다.

식으로 나타내면,

(x2,y2)까지의 부분합 - (A+B) - (A+C) + A 가 된다.

A부분이 두번 빼지니까 마지막에 한 번 더 더해주면 된다.

 

코드

---

# https://www.acmicpc.net/problem/11660
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [[0]*(N+1)]
for _ in range(N):
    dp.append([0] + list(map(int, input().strip().split())))
target = []
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    target.append([x1, y1, x2, y2])

# row accumulation
for i in range(1, N+1):
    for j in range(2,N+1):
        dp[i][j] += dp[i][j-1]
# col accumulation
for i in range(1, N+1):
    for j in range(2, N+1):
        dp[j][i] += dp[j-1][i]

for x1, y1, x2, y2 in target:
    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])