[백준] 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

누적 합(Cumulative sum)을 이용해 구간 합(Prefix sum)을 구하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 2d array가 주어질 떄, 해당하는 array의 (x1, y1)와 (x2, y2)가 이루는 직사각형 면적 내부의 원소들의 합을 구해야 하는 문제입니다. 

 

<Solution>

누적 합을 통한 구간 합을 이용하는 문제입니다.

간단한 예시를 통해 설명해보겠습니다.

왼쪽과 같은 array가 주어진다고 생각해봅시다. 그러면 누적합을 구하면 오른쪽처럼 바뀝니다. 둘레에 있는 0은 편리한 계산을 위해 두는 것입니다. 이 누적 합은 가장 처음의 array상태에서 row방향으로 누적 합 한번, column 방향으로 누적 합 한번을 해주면 됩니다.  

 

이렇게 되면 

다음과 같이 42가 의미하는 바는 위의 녹색으로 둘러친 부분의 합인 것을 알 수 있습니다. 그렇다면 특정 직사각형 내부의 넓이는 어떻게 구하면 될지 생각해보면, 

다음과 같이 관계를 쉽게 찾아 낼 수 있습니다. 각각의 누적합을 이용해 부분합을 적절히 구성하는 방법입니다.

 

실제 구현은 아래와 같습니다.(코드 상에서 prefix sum array라고 두었는데 사실 cummulative sum array라는 표현이 좀 더 정확 할 것 같습니다.) 

import sys

N, M = list(map(int, sys.stdin.readline().rstrip().split()))

array = []
for _ in range(N):
    array.append(list(map(int, sys.stdin.readline().rstrip().split())))

# build prefix sum array
prefix_sum_array = [[0]*(N+1)]
for row in array:
    new_row = [0] + row
    for i in range(1, len(new_row)):
        new_row[i] = new_row[i-1] + new_row[i]
    prefix_sum_array.append(new_row)

for i, row in enumerate(prefix_sum_array[1:]):
    prefix_sum_array[i+1] = [a+b for a,b in zip(prefix_sum_array[i],prefix_sum_array[i+1])]
###

for _ in range(M):
    x1, y1, x2, y2 = list(map(int, sys.stdin.readline().rstrip().split()))
    a = prefix_sum_array[x2][y2]
    b = prefix_sum_array[x2][y1-1]
    c = prefix_sum_array[x1-1][y2]
    d = prefix_sum_array[x1-1][y1-1]

    print(a+d-b-c)