[백준] 2차원 배열의 합

누적합

합들의 값을 미리 더해두는 것을 누적 합이라고 한다.

누적합의 예

A = [i for i in range(10)]
print(A)
for i in range(1, 10):
	A[i] = A[i-1] + A[i]
print(A)

DP[i] = i까지 합

i부터 j까지의 합은 DP[i] - DP[j-1]

 

 

 

<구현으로 인한 풀이>

n, m = map(int, input().split())
lst = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1, n+1):
    tmp = list(map(int, input().split()))
    for j in range(1, m+1):
        lst[i][j] = tmp[j-1]

k = int(input())
k_lst = [list(map(int, input().split())) for _ in range(k)]
result = []

for u in range(k):
    a,b,x,y = k_lst[u][0], k_lst[u][1], k_lst[u][2], k_lst[u][3]
    sum = 0
    for i in range(a,x+1):
        for j in range(b, y+1):
            sum += lst[i][j]
    result.append(sum)

for i in range(len(result)):
    print(result[i])

<DP를 활용한 풀이>

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# DP[i][j] = 1, 1부터 (i, j)까지의 부분합
DP = [[0 for i in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
        
for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])