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

📖 문제

📖 예제

📖 풀이

import sys
input = sys.stdin.readline

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

dp = [[0]* (N+1) for _ in range(N+1)]

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] + graph[i-1][j-1]
    
for _ in range(M):
  x1, y1, x2, y2 = map(int, input().split())
  ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

  print(ans)

dp에 누적합을 미리 구해놓는다.
후에 x1, y1, x2, y2 값을 입력으로 받아 다음 점화식을 통해 답을 구한다.
ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] dp[x1-1][y1-1]