[dp/백준] 11660번: 구간 합 구하기 5

-문제: https://www.acmicpc.net/problem/11660

 

완전 탐색으로 하면 되는 쉬운 문제인 줄 알았는데, 시간 초과가 떴다.

그래서 찾아보니 dp로 (0,0)부터 (i,j)까지의 합을 저장한후 이를 이용하는 문제였다

 

이 풀이에서 가장 이해가 안가는 부분이다.

i+1,j+1까지의 합을 구하면 data[i][j]가 아니라 data[i+1][j+1]을 더해야 하는게 아닌가? 싶은 생각인데

실제 행렬 위치와 주어진 행렬 위치가 다르므로 그걸 생각해서 한 것같다. 이 부분은 좀 더 해봐야 할 것 같다

#(0,0)부터 (i,j)까지의 합이 dp[i+1][j+1]에 저장됨
        dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+data[i][j]

 

-정답풀이:

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        #(0,0)부터 (i,j)까지의 합이 dp[i+1][j+1]에 저장됨
        dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+data[i][j]
for _ in range(m):
    a,b,c,d=map(int,input().split())
    print(dp[c][d]-(dp[c][b-1]+dp[a-1][d]-dp[a-1][b-1]))