[DP] - S1_11660_구간합 구하기 5

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

11660번: 구간 합 구하기 5

📌 - 문제 해결 방법

구해야 하는 횟수가 10만이기 때문에 시간초과가 날 수 있기 때문에 DP로 문제를 해결해야한다.

먼저 해당하는 전체 구간의 합들을 DP배열에 갱신을 한다.

해당하는 구간의 합을 구하는 방법은 

해당하는 칸의 구간합 -> dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j]

 

DP로 전체 구간합

 

 

구한 DP표를 가지고 해당하는 구간의 합을 구한다.

구간의 합을 구할 때는 (0,0)부터 원하는 좌표의 값까지 구간합에서 해당하지 않는 구간 합들을 빼주면 되는데

여기서 중요한 점은 아래의 예시와 같이 (0,0)의 값은 2번 빼게 되기 때문에 1번 더해줘야 정확한 답이 나온다.

 

📌 -  (1,1)~(2,2)를 구하는 예시
- (1,1) ~ (2,2) 을 구한다고 생각했을 때
- (2,2) - (0,2) - (2,0) + (0,0) = (1,1) ~ (2,2)의 값

dp[x2][y2]- dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

 

 

3,3을 구할때

 

 

 

from sys import stdin as s

s = open('input.txt','rt')

N, M = list(map(int,s.readline().split()))

arr = [list(map(int,s.readline().split())) for _ in range(N)]
dp = [[0]* (N+1) for _ in range(N+1)]

temp = [list(map(int,s.readline().split())) for _ in range(M)]

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] + arr[i-1][j-1]


for x1,y1,x2,y2 in temp:
    result = dp[x2][y2]- dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(result)