백준 16507: 어두운 건 무서워

문제 요약

호근이에게 보여줄 R×C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 밝기 평균을 구하여라.

문제 분류

• 누적 합

문제 풀이

입력된 값을 저장할 필요 없이 바로 누적 합 배열로 누적시키며 저장시키면 된다.

각 i번째 행을 j열까지 누적시킨 값, S[i][j]를 만들어서, S[i][c2] - S[i][c1 - 1]를 누적시키면 된다. 이때, 열은 0번 인덱스가 0이므로 상관이 없었지만, 행은 0번 인덱스부터 바로 시작하므로 r1과 r2에 1을 뺀 값으로 넣어주어서 계산하면 된다. 즉, i는 r1 - 1 부터 r2 - 1을 포함한 값까지 돌아야 할 것이다.

그리고 r1 <= r2, c1 <= c2 이므로 직사각형 내의 원소 개수는 (r2 - r1 + 1) * (c2 - c1 + 1)이 될 것이다. 누적시킨 값에 해당값으로 나눈 몫을 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int S[1001][1001];

int main() {
	int r, c, q, in;
	int r1, c1, r2, c2, res;
	scanf("%d%d%d", &r, &c, &q);
	for (int i = 0; i < r; i++) {
		for (int j = 1; j <= c; j++) {
			scanf("%d", &in);
			S[i][j] = S[i][j - 1] + in;
		}
	}
	while (q--) {
		scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
		res = 0;
		for (int i = r1 - 1; i <= r2 - 1; i++)
			res += (S[i][c2] - S[i][c1 - 1]);
		printf("%d\n", res/ ((r2 - r1 + 1) * (c2 - c1 + 1)));
	}
	return 0;
}