백준[16507] 어두운 건 무서워

문제 설명

문제 링크

http://icpc.me/16507

16507번: 어두운 건 무서워

풀이

2차원 누적합으로 풀 수 있다.

누적합을 이용하지 않고 푼다면 주어진 쿼리를 모두 확인하는 방식으로 푼다면 O(RCQ)로 10억이 넘어가 시간이 터질 것이다.

그렇기 때문에 누적합을 이용하여 쿼리당 O(1)에 구간 합을 구해야 한다.

psum [i][j] : 오른쪽 아래 꼭짓점이 (i, j)에 있을 때 내부에 있는 밝기의 합이라고 할 때,

psum [i][j]는 아래 그림에서 (빨강 + 초록 - 노랑 + 파랑)으로 구할 수 있다

psum

부분 합은 빨강 - 초록 2개 + 파란 네모로 구할 수 있다.

부분 합

평균을 구하기 위해 나눌 수는 (c - a + 1) * (d - b + 1)이다.

코드

#include <cstdio>

int arr[1003][1003];
int psum[1003][1003];

int main() {
    int n, m, q; scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &arr[i][j]);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + arr[i][j];
        }
    }

    while (q--) {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        int sum = psum[c][d] - psum[c][b - 1] - psum[a - 1][d] + psum[a - 1][b - 1];
        int div = (c - a + 1) * (d - b + 1);
        printf("%d\n", sum / div);
    }
}