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

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)

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

// 14846. 직사각형과 쿼리
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vector<vector<vector<int>>> vec(n + 1, vector<vector<int>>(n + 1, vector<int>(12, 0)));
    vector<vector<vector<int>>> prefix(n + 1, vector<vector<int>>(n + 1, vector<int>(12, 0)));
 
    int temp;
    // 원본 배열 입력 받아주기
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            cin >> temp;
            vec[i][j][temp]++;
        }
    }
 
    // 누적합 배열 생성 (자연수의 개수에 대한 누적합)
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            // 1부터 10까지에 대한 for문
            for (int k = 1; k < 11; k++)
            {
                prefix[i][j][k] = prefix[i - 1][j][k] + prefix[i][j - 1][k] - prefix[i - 1][j - 1][k] + vec[i][j][k];
            }
        }
    }
    
    cin >> temp;
 
    int a, b, c, d;
    
    for (int i = 0; i < temp; i++)
    {
        cin >> a >> b >> c >> d;
        int answer = 0;
        for (int j = 1; j < 11; j++)
        {
            int result = prefix[c][d][j] - prefix[a - 1][d][j] - prefix[c][b - 1][j] + prefix[a - 1][b - 1][j];
            if (result > 0) answer++;
        }
        cout << answer << '\n';
    }
 
    return 0;
}

---

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

14846번: 직사각형과 쿼리