[백준 16507] 어두운 건 무서워 (C++)

https://www.acmicpc.net/problem/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)를 꼭짓점으로 하는 직사각형의 밝기 평균을 출력한다. 평균은 정수 나눗셈으로 몫만 취한다.

 

문제 풀이

---

2차원 누적합 문제.

 

1, 1칸부터 특정 칸까지의 합을 구해야 한다. 첫번째 행과 열은 이전의 값을 더하면 되므로 쉽다. (1, 1)칸이 a, (1,2)이 b, (2,1)이 c, (2,2)칸이 d라고 할 때 채워야 하는 칸은 다음과 같다.

 

a	a + b
a+c	a+b+c+d

(2, 2)를 구할 때 a+b인 (1, 2)까지의 합과 a+c인 (2, 1)까지의 합을 더한 후 중복된 값인 a(= 1, 1까지의 합)을 빼면 그 값을 얻을 수 있다.

 

(1, 1)부터가 아닌 (r1, c1)부터 (r2, c2)까지의 합도 비슷한 방식으로 구해주면 된다.

 

 

(2, 2)부터 (3, 3)까지를 구하고 싶다면 (3, 3)까지의 합에서 (1, 3)까지의 합, (3, 1)까지의 합을 빼준 후 중복으로 빼준 값인 (1, 1)까지의 합을 더하면 그 답을 얻을 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int R, C, Q;
	int r1, c1, r2, c2;
	cin >> R >> C >> Q;
	int** photo = new int*[R];
	long long** sums = new long long*[R+1];
	for (int i = 0; i < R + 1; i++)
	{
		sums[i] = new long long[C + 1];
		for (int j = 0; j < C+1; j++)
		{
			sums[i][j] = 0;
		}
	}
	for (int i = 0; i < R; i++)
	{
		photo[i] = new int[C];
		for (int j = 0; j < C; j++)
		{
			cin >> photo[i][j];
		}
	}
	sums[1][1] = photo[0][0];
	for (int i = 1; i < R+1; i++)
	{
		sums[i][1] = sums[i - 1][1] + photo[i-1][0];
	}
	for (int j = 1; j < C+1; j++)
	{
		sums[1][j] = sums[1][j - 1] + photo[0][j-1];
	}
	for (int i = 2; i < R+1; i++)
	{
		for (int j = 2; j < C+1; j++)
		{
			sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + photo[i-1][j-1];
		}
	}
	for (int i = 0; i < Q; i++)
	{
		cin >> r1 >> c1 >> r2 >> c2;
		int pixelCount = (r2 - r1 + 1) * (c2 - c1+1);
		long long sum = sums[r2][c2] - sums[r2][c1 - 1] - sums[r1 - 1][c2] + sums[r1 - 1][c1 - 1];
		cout <<sum / pixelCount<<"\n";
	}
	return 0;
}