C++[백준]14846번 직사각형과 쿼리

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

14846번: 직사각형과 쿼리

 

솔루션

---

특정 인덱스(x,y)에서 1~10의 수를 몇개씩  갖고있는지 저장해둔다.

 

나는 구조체 내부에 배열을 선언하여, 1~10까지 몇 번 등장했는지, 저장해둔다.

 

특정 인덱스에서의 등장횟수를 찾는 법은

1. 현재 인덱스에 배열의 값을 ++

2. [x-1][y]에서의 등장 횟수 + [x][y-1]에서의 등장 횟수 - [x-1][y-1]에서의 등장횟수를 해 주면 특정 인덱스에서의 총 등장횟수를 알 수 있다.

 

그리고 각 쿼리에 대해서 값을 알아낼 땐,

 [x2][y2] 값에서 -[x2][y1-1] - [x1-1][y2] + [x1-1][y1-1]를 해 주면 구할 수 있다.

 

(누적합 매트릭스에서 자주 쓰이는 식이라.. 다른 곳에 찾아보면 이해하기 쉽게 적어 놓은 곳이 많을 것이다.)

 

 

 

코드

---

#include <iostream>
using namespace std;

struct pa {
	int value[11] = { 0, };

	void operator-=(const struct pa& t) {
		for (int i = 1; i <= 10; i++) {
			this->value[i] -= t.value[i];
		}
	}
	void operator+=(const struct pa& t) {
		for (int i = 1; i <= 10; i++) {
			this->value[i] += t.value[i];
		}
	}
};

int N;
struct pa dp[302][302];
int arr[302][302];

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

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

	dp[1][1].value[arr[1][1]]++;
	for (int i = 2; i <= N; i++) {
		dp[i][1].value[arr[i][1]]++;
		dp[i][1] += dp[i - 1][1];
		dp[1][i].value[arr[1][i]]++;
		dp[1][i] += dp[1][i - 1];
	}
	for (int i = 2; i <= N; i++) {
		for (int j = 2; j <= N; j++) {
			dp[i][j].value[arr[i][j]]++;
			dp[i][j] += dp[i - 1][j];
			dp[i][j] += dp[i][j - 1];
			dp[i][j] -= dp[i - 1][j - 1];
		}
	}

	int Q;
	cin >> Q;

	while (Q--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		struct pa t = dp[x2][y2];

		t -= dp[x2][y1-1];
		t -= dp[x1-1][y2];
		t += dp[x1 - 1][y1 - 1];
		int cnt = 0;
		for (int i = 1; i <= 10; i++) {
			if (t.value[i] > 0) {
				cnt++;
			}
		}
		cout << cnt << '\n';
	}
}