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

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

11660번: 구간 합 구하기 5

문제 한줄 이해

-N*N 의 그래프가 주어질때 (x1,y1) - (x2,y2)까지의 합 구하기

 

생각난 풀이

1번째 방법: 문제 이름이 대놓고 누적합이라 어떤식으로 디피에 저장을 해서 이용을 할까 생각을 했다. 

이때 dp에 그래프를 순차적으로 돌면서 합을 저장 해놓고 이를 활용 하면 된다고 생각 했다. 

이유는 그림에서 설명한거 처럼 구하고자 하는 범위까지 더해 놓은 dp값에 범위 직전에 값을 뺀다면 구하려고 하는 부분들을 찾아 낼수 있다.

 

import sys
from collections import deque
n, m = map(int,sys.stdin.readline().split())
graph = []
mlist = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
    
for i in range(m):
    mlist.append(list(map(int,sys.stdin.readline().split())))
    
dp = [[0 for i in range(n+1)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(n+1):
        if j != 0 and j != 1:
            dp[i][j] = dp[i][j-1] + graph[i-1][j-1]
        elif j == 0:
            dp[i][j] = dp[i-1][n]
        elif j == 1 :
            dp[i][j] = dp[i-1][n] + graph[i-1][j-1]
            
for x1,y1,x2,y2 in mlist:
    result = 0
    for i in range(x1,x2+1):
        result += dp[i][y2] - dp[i][y1-1]
    print(result)