11660 - 구간 합 구하기 5 / silver 1 / DP

"""
11660 - 구간 합 구하기 5 / silver 1
"""
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = []

for _ in range(n):
    arr.append(list(map(int, input().split())))

for _ in range(m):
    res = 0
    x, y, p, q = map(int, input().split())
    for i in range(x - 1, p):
        for j in range(y - 1, q):
            res += arr[i][j]
    print(res)

- 시간 초과

 

"""
11660 - 구간 합 구하기 5 / silver 1 / DP
"""
import sys

input = sys.stdin.readline


# 1. Input
n, m = map(int, input().split())

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

# 2. DP / 구간 합
for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) + arr[i][j]

# 3. 출력
for _ in range(m):
    x, y, p, q = map(int, input().split())
    print(dp[p][q] - (dp[x - 1][q] + dp[p][y - 1] - dp[x - 1][y - 1]))

DP 리스트 - 구간 합 넣기

arr / dp 리스트

DP 리스트 - 출력 

dp 리스트

- 연두색 네모 : 원래 arr 에서 구해야하는 구간

- 현재 dp리스트 안에 있는 값들은 처음부터(1,1) 자신 인덱스(i,j) 까지 구간 합

 

DP 리스트에서 원하는 결과 값 얻기

빨강 - (주황+ 노랑 - 파랑)

==

dp[p][q] - (dp[x - 1][q] + dp[p][y - 1] - dp[x - 1][y - 1])