BOJ 16507 - 어두운 건 무서워 링크
(2023.09.26 기준 S1)

문제

R×C 크기의 사진이 있으며 각 픽셀마다의 밝기가 주어진다.
Q개의 쿼리마다 r1, c1, r2, c2가 주어진다. 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균 출력

알고리즘

2차원 누적 합

풀이

(r1, c1) ~ (r2, c2) 까지의 구간 합을 구해야 한다.
그러면 일단 연노랑 영역 prefix_sum[r2][c2]에서 노랑 영역 prefix_sum[r2][c1-1]과 초록 영역 prefix_sum[r1-1][c2]을 빼보자. 그러면 (0, 0) ~ (r1-1, c1-1) 까지의 영역이 두 번 빠지게 된다. 그러므로 빨강 영역 prefix_sum[r1-1][c1-]을 더해주면 된다.

이렇게 구간 합을 구한 뒤, 밝기 평균을 구해야 하므로 구간의 크기로 나눠서 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int R, C, Q; cin >> R >> C >> Q;

    int matrix[R + 1][C + 1]; fill(&matrix[0][0], &matrix[R][C + 1], 0);
    for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) cin >> matrix[i][j];

    // 누적 합 행렬
    int prefix_sum[R + 1][C + 1]; fill(&prefix_sum[0][0], &prefix_sum[R][C + 1], 0);
    for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++)
        prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + matrix[i][j];
    
    // 구간 합 쿼리 결과를 구간의 크기로 나눠서 출력
    for (int r1, c1, r2, c2; Q; Q--){
        cin >> r1 >> c1 >> r2 >> c2;
        cout << (prefix_sum[r2][c2] - prefix_sum[r1 - 1][c2] - prefix_sum[r2][c1 - 1] + prefix_sum[r1 - 1][c1 - 1]) / ((r2 - r1 + 1) * (c2 - c1 + 1)) << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline

R, C, Q = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(R)]

# 누적 합 행렬
prefix_sum = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + matrix[i - 1][j - 1]

# 구간 합 쿼리 결과를 구간의 크기로 나눠서 출력
for _ in range(Q):
    r1, c1, r2, c2 = map(int, input().split())
    print((prefix_sum[r2][c2] - prefix_sum[r1 - 1][c2] - prefix_sum[r2][c1 - 1] + prefix_sum[r1 - 1][c1 - 1]) // ((r2 - r1 + 1) * (c2 - c1 + 1)))