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

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

www.acmicpc.net/problem/16507

16507번: 어두운 건 무서워

 

 

 문제

 호근이는 겁이 많아 어두운 것을 싫어한다. 호근이에게 어떤 사진을 보여주려는데 사진의 밝기가 평균 이상이 되지 않으면 일절 보려 하지 않는다. 호근이가 이 사진에서 일부분이라도 볼 수 있는 부분을 찾아주자.

 위 그림은 호근이에게 보여줄 5×6 크기의 사진이며, 각 픽셀은 밝기를 나타낸다. 호근이가 사진의 일부분이라도 볼 수 있는지 알아보기 위해서는 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 구해야 한다. 예를 들어, 위 그림에서는 (2, 2)와 (4, 5)를 꼭짓점으로 하는 직사각형을 말한다.

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

 

 입력

 첫 번째 줄에는 사진의 크기를 의미하는 정수 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)를 꼭짓점으로 하는 직사각형의 밝기 평균을 출력한다. 평균은 정수 나눗셈으로 몫만 취한다.

 

 

 풀이

#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int R, C, K; cin >> R >> C >> K;
	int dd[1001][1001]={0,};
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			cin >> dd[i][j];
			dd[i][j] += dd[i-1][j] + dd[i][j-1] - dd[i-1][j-1];
		}
	}
	
	for(int i=0;i<K;i++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int s = dd[c][d] - dd[a-1][d] - dd[c][b-1] + dd[a-1][b-1];
		int z = (c-a+1) * (d-b+1);
		cout << s / z << '\n';
	}
	return 0;
}

 2차원 배열에서의 누적합 문제이다. dd[i][j]는 (0~i) * (0~j) 의 합으로 구성된다. 2167번 2차원 배열의 합 문제를 풀었다면 쉽게 풀 수 있는 문제인데 난이도 차이가 너무 많이 차이나는 것 같다.