[백준/Python] 11660번 - 구간 합 구하기 5

문제

백준 11660번 - 구간 합 구하기 5

해결 과정

• 누적합 구하기

시행착오

• 시간초과 -> DP로 풀기

import sys


n, m = map(int,sys.stdin.readline().split())


graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

res= []

for _ in range(m):
  x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
  answer = 0
  for i in range(x1-1,x2):
    for j  in range(y1-1,y2):
      answer += graph[i][j] 
  res.append(answer)
  

for r in res:
  print(r)

풀이

import sys

n, m = map(int,sys.stdin.readline().split())

graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

sum_arr = [[0] * (n+1) for _ in range(n+1)]

# 누적합 배열 만들기
for i in range(1,n+1):
  for j in range(1,n+1):
    sum_arr[i][j] = graph[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

for _ in range(m):
  x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
  print(sum_arr[x2][y2] - sum_arr[x1-1][y2]-sum_arr[x2][y1-1]+sum_arr[x1-1][y1-1])