[C++] BOJ(백준) 14846 직사각형과 쿼리

[https://www.acmicpc.net/problem/14846

14846번: 직사각형과 쿼리

 

DP와 누적합 문제다.

 

해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다.

배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다.

검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다.

빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야한다.

 

쿼리의 범위가 검정색 부분이라면 위와 반대로 진행하면 된다.

검정색 오른쪽 아래 부분의 누적 합에서 빨간 부분과 파란 부분을 빼주고,

보라 부분이 두 번 빠지기 때문에 한 번 더해준다.

 

#include <iostream>
using namespace std;

int n, m;
int arr[301][301];
int sumsum[301][301][11];

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> arr[i][j];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= 10; k++) {
				sumsum[i][j][k] = (sumsum[i - 1][j][k]
					+ sumsum[i][j - 1][k]
					- sumsum[i - 1][j - 1][k]);
				sumsum[i][j][arr[i][j]]++;
			}

	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c, d;	cin >> a >> b >> c >> d;
		int cnt = 0, res[11] = { 0 };

		for (int k = 1; k <= 10; k++) {
			res[k] = (sumsum[c][d][k]
				- sumsum[a - 1][d][k]
				- sumsum[c][b - 1][k]
				+ sumsum[a - 1][b - 1][k]);
		}

		for (int k = 1; k <= 10; k++)
			if (res[k]) cnt++;
		cout << cnt << "\n";
	}
}