[Python] 11660번 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

---

 

22/09/17

 

 

이전에 누적 합 문제를 풀어 본 적이 있었는데, 그때를 경험 삼아서 이 문제도 풀 수 있을 것 같아 풀게 된 문제다.

 

전형적인 누적 합, DP문제이다.

---

 

문제 접근 방식:

 

 

표의 크기가 주어지고(N = ~1024) 쿼리의 크기가 10만까지 주어지는데, 한 쿼리 마다 표의 연산을 전부 처리한다는 극단적인 케이스를 가정한다면, 1024*1024*10만이어서 대략 100만*10만이라는 무지막지하게 큰 숫자가 나온다.

 

때문에 한 쿼리에서 요구하는 연산을 줄이기 위해 미리 계산해 놓은 값을 이용하여 인덱스로만 접근하게끔 문제를 풀게 할 것이다.

 

문제에서 요구하는 기본적인 아이디어는 다음과 같다.

예시

위의 그림을 보자.

 

우리는 2행 2열부터 3행 4열까지의 합(빨간색 직사각형으로 둘러싸인 숫자들)을 구하고자 한다.

 

또한, 1행 1열부터 n행 m열까지의 합을 S(n,m)이라고 해보자.

 

이때, 어떤 식으로 주어지든지 간에 우리가 구하고자 하는 구간합의 모양은 직사각형이기 때문에 S(n, m)끼리의 차와 합으로 구성할 수 있다!

 

위의 예시에서는 빨간부분의 합을 구하기 위해 (파란 부분의 합) - (보라 부분의 합) - (초록 부분의 합) + (노란 부분의 합)을 통해서 구해주었다.

 

어떻게 보면 일종의 포함배제의 원리가 적용된 사례라고 볼 수 있다.

 

결국 우리는 S(n, m)들을 미리 구해놓고, 이것의 인덱스들에 접근함으로써 하나의 쿼리를 O(1)에 가까운 시간으로 처리할 수 있는 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11660번 구간 합 구하기 5
# DP, 누적 합
'''
접근 방법:
(x1, y1) ~ (x2, y2)까지의 합 구하는 법
누적 합 배열에서(x2, y2) - (x2, y1-1) - (x1-1, y2) + (x1-1, y1-1)
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]
accum_sum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for row in range(1, N+1):
    for col in range(1, N+1):
        accum_sum[row][col] = accum_sum[row-1][col] + sum(matrix[row-1][:col])

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    print(accum_sum[x2][y2] - accum_sum[x2][y1-1] - accum_sum[x1-1][y2] + accum_sum[x1-1][y1-1])