백준 11660번. 구간 합 구하기 5 (Python / 파이썬)

문제 

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

---

문제 풀이 

(x1, y1) 부터 (x2, y2) 까지의 합을 구하기 위해서는 그냥 탐색하면서 하나씩 더해주면 된다. 

하지만 해당 문제에서 제시된 표의 크기가 매우 크기 때문에 하나하나 탐색하면서 더해주면 시간초과 문제가 발생하게 된다. 따라서 시간 초과 문제를 해결하기 위해 좀 더 효율적인 방법을 생각해야 한다. 

 

일단, 우리가 궁금한건 합이므로 누적합을 구해서 결과를 저장해두어야 한다. 

맨 왼쪽 맨 위로부터 노란색 칸 까지의 누적합을 구하기 위해서 (x, y-1) 까지 구해둔 합과 (x-1, y) 까지 구해둔 합을 활용한다. 두 칸까지 구해둔 누적합을 더하면 노란색 칸까지의 누적합을 구할 수 있다. 

이때, 두 칸까지의 합을 더해버리면 위의 그림에서 빨간색 부분을 2번 더하는 것이 되므로 이 부분을 빼주어야 한다. 

이 과정을 통해 각 칸까지의 누적합을 구할 수 있다. 

 

이제 이 누적합을 이용해서 구간 합을 구해주면 된다. 

(x2, y2) 에 저장된 누적합에서 (x2, y1-1), (x1-1, y2) 에 저장된 누적합을 빼주면 (x1, y1)에서 (x2, y2) 까지의 구간 합을 구할 수 있다. 

이때, 빨간색 부분은 2번 빼주게 되므로 이 부분을 더해주어야 한다. 

이처럼 DP를 이용해서 각 칸까지의 누적합을 먼저 구해주고 그 누적합들을 이용하여 구간 합을 효율적으로 빠른 시간 내에 구할 수 있게 된다. 

---

My Code

import sys 
input = sys.stdin.readline

n, m = map(int,input().split())

array = []
for _ in range(n):
    array.append(list(map(int,input().split())))

sum_dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        sum_dp[i][j] = sum_dp[i][j-1] + sum_dp[i-1][j] - sum_dp[i-1][j-1] + array[i-1][j-1]

for _ in range(m):
    x1, y1, x2, y2 = map(int,input().split())

    ans = sum_dp[x2][y2] - sum_dp[x2][y1-1] - sum_dp[x1-1][y2] + sum_dp[x1-1][y1-1]
    print(ans)