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

문제 링크

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

14846번: 직사각형과 쿼리

 

문제

N행 N열로 이루어진 정사각형 행렬 A가 주어진다. 이때, 쿼리를 수행하는 프로그램을 작성하시오.

• x1 y1 x2 y2: 왼쪽 윗칸이 (x1, y1)이고, 오른쪽 아랫칸이 (x2, y2)인 부분 행렬에 포함되어 있는 서로 다른 정수의 개수를 출력한다.

입력

첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며, 번호는 1번부터 시작한다. 행렬이 포함하고 있는 정수는 10보다 작거나 같은 자연수이다.

다음 줄에는 Q (1 ≤ Q ≤ 100,000)가 주어진다. 다음 Q개의 줄에는 쿼리의 정보 x1, y1, x2, y2가 주어진다. (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n)

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

3
1 2 3
3 2 1
5 6 3
3
1 1 2 3
2 2 2 2
1 1 3 3

예제 출력 1

3
1
5

알고리즘 분류

• 누적 합

풀이

다행히 1부터 10까지의 자연수만 입력받기 때문에, Sum[300][300][10]이라는 3차원 배열을 선언해준다. 이것은 (1, 1)부터 (A, B)까지 자연수 C의 개수를 의미하는 것이다.

이제 Q개의 쿼리를 수행한다. 1부터 10까지 각각 누적 합의 개수를 구해 해당 구간의 자연수 i에 대한 누적 합이 0이라면 그 자연수는 해당 구간에 없는 것이고, 0이 아니라면 있는 것이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 301
#define LL long long
#define INF 1e9

using namespace std;
int N, Q;
int Sum[MAX][MAX][11];

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int A;
			cin >> A;
			for (int k = 1; k <= 10; k++) {
				Sum[i][j][k] = Sum[i - 1][j][k] + Sum[i][j - 1][k] - Sum[i - 1][j - 1][k] + (k == A ? 1 : 0);
			}
		}
	}
	cin >> Q;
}

void Find_Answer() {
	while (Q--) {
		int X1, Y1, X2, Y2;
		cin >> X1 >> Y1 >> X2 >> Y2;
		int Answer = 0;
		for (int i = 1; i <= 10; i++) {
			int Cur = Sum[X2][Y2][i] - Sum[X2][Y1 - 1][i] - Sum[X1 - 1][Y2][i] + Sum[X1 - 1][Y1 - 1][i];
			if (Cur != 0) {
				Answer++;
			}
		}
		cout << Answer << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}