개요

백준 16507: 어두운 건 무서워

• 입력
  첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다.

  다음 R개의 줄에 걸쳐 R×C 크기의 사진 정보가 주어지며, 사진의 각 픽셀에는 밝기를 의미하는 정수 K (1 ≤ K ≤ 1,000)가 주어진다.

  다음 Q개의 각 줄에는 사진의 일부분을 나타내기 위한 두 꼭짓점을 의미하는 정수 r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C)가 주어진다.

• 출력
  Q개의 각 줄에 주어진 사진에서 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 출력한다. 평균은 정수 나눗셈으로 몫만 취한다.

접근 방식

1. 백준11660번: 구간 합 구하기 5 문제와 아주 유사하다.
   저 풀이에서 마지막에 구간의 원소 갯수를 나눠주기만 하면 된다.

2. 구간합배열을 바로 알 수 있도록 누적합 배열을 저장할 2차원배열을 생성해주었다.

   	cin >> R >> C >> Q;
   		for (int i = 0; i < R; i++) {
   			for (int j = 0; j < C; j++) {
   			 cin >> brightness;
   			 //Sum[i+1][j+1]은 i,j값까지의 합
   			 Sum[i + 1][j + 1] = Sum[i + 1][j] + Sum[i][j + 1] - Sum[i][j] + brightness;
           }

   i,j까지의 모든 합은
   i,j-1까지의 합+ i-1,j까지의 합 - 중복되는 i-1,j-1 까지의 합 + i,j 좌표값 이다.

3. 따라서 해당 구간의 합은

	for (int i = 0; i < Q; i++) {
		//시작 좌표, 끝좌표 받은 후,
		cin >> tmpX1 >> tmpY1>>tmpX2>>tmpY2;
		//답은 해당 구역의 총 합 / 해당 구역의 원소 갯수
		Ans = (Sum[tmpX2][tmpY2]-Sum[tmpX1-1][tmpY2]-Sum[tmpX2][tmpY1-1] + Sum[tmpX1-1][tmpY1-1]) / ((tmpX2-tmpX1+1)*(tmpY2-tmpY1+1));

이런식으로 구할 수 있다.
2 2 4 5가 들어왔다면
4,5까지의 모든 합 - 1,5까지의 모든합 - 4,1까지의 모든 합 + 1,1까지의 합 / 해당 구간안의 원소의 갯수

전체 코드

#include<iostream>

using namespace std;
int R=0, C=0, Q = 0;
int Sum[1'001][1001];

void Input() {
	int brightness=0,tmpX1=0,tmpX2=0,tmpY1=0,tmpY2=0,Ans=0;
	cin >> R >> C >> Q;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> brightness;
			//Sum[i+1][j+1]은 i,j값까지의 합
			Sum[i + 1][j + 1] = Sum[i + 1][j] + Sum[i][j + 1] - Sum[i][j] + brightness;
		}
	}
	for (int i = 0; i < Q; i++) {
		//시작 좌표, 끝좌표 받은 후,
		cin >> tmpX1 >> tmpY1>>tmpX2>>tmpY2;
		//답은 해당 구역의 총 합 / 해당 구역의 원소 갯수
		Ans = (Sum[tmpX2][tmpY2]-Sum[tmpX1-1][tmpY2]-Sum[tmpX2][tmpY1-1] + Sum[tmpX1-1][tmpY1-1]) / ((tmpX2-tmpX1+1)*(tmpY2-tmpY1+1));
		cout << Ans <<'\n';
	}
}




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

문풀후생

답 구하는 부분이 좀 인덱스 부분도 그렇고 애매하긴하지만
Sum배열이 확실히 i,j까지의 합을 저장하는 배열이란걸 알면 점화식은 세우기 쉽다