[C/C++] 백준 #2167 2차원 배열의 합(포함배제 원리)

#2167 문제는 2차원 배열 공간에서 사각형으로 지정한 공간에 있는 숫자합을 계산해야 합니다.  지정된 공간의 합을 한번 계산하는 것이라면, 이중 반복문을 이용해서 풀면 되겠지만, 여기는 K개의 질의(query)가 있기때문에 단순하게 처리하면 \(O(KNM)\)이라는 시간 복잡도를 가지게 됩니다.

 

문제의 링크는 다음과 같습니다.

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

2167번: 2차원 배열의 합

 

이 문제는 (0, 0)을 시작점으로 해서 (r, c)까지의 배열 합을 미리 구해서 처리합니다.  (r, c)의 값을 \(w_{r, c}\)라고 한다면, (0, 0)부터의 합은 다음과 같이 계산할 수 있습니다.

 

\[ S_{r, c} = S_{r, c-1} + S_{r-1, c} - S_{r-1, c-1} + w_{r, c} \]

 

위의 식은 포함배제의 원리에 의해서 계산된 것입니다.  그러면 포함배제의 원리는 어떤 것인가하면요,

 

inclusion-exclusion principle

우리가 (0,0) - (r, c)까지의 영역을 모두 (r, c)셀에 기록을 했다고 한다면, D의 영역은 위의 그림과 같이 포함배제 원리에 의해서 구할 수가 있습니다.  벤 다이어그램에서 합집합의 크기를 계산할 때에도 포함배제 원리를 적용할 수 있습니다.

 

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2167
//        - by Aubrey Choi
//        - created at 2019-07-06
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, s;
    static int v[301][301];
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &s);
            v[i][j] = v[i][j - 1] + v[i - 1][j] - v[i - 1][j - 1] + s;
        }
    }
    scanf("%d", &s);
    while(s--)
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", v[x2][y2] - v[x1 - 1][y2] - v[x2][y1 - 1] + v[x1 - 1][y1 - 1]);
    }
    return 0;
}