[baekjoon] 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)

출력

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

예제 입력

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

예제 출력

3
1
5

풀이

쿼리가 최대 10만개 이기 때문에 매번 탐색을 돌리기엔 시간이 많이 소요된다.

행렬이 포함하고 있는 정수의 범위가 1 ≤  K ≤ 10 이고, 1  ≤ N ≤ 300 이기 때문에 충분히 DP를 구성할 수 있다.

DP [K][X][Y]의 의미는 XY에 포함된 K의 개수이다.DP [X][Y] = DP [X-1][Y] + DP [X][Y-1] - DP [X-1][Y-1] 이 된다.

1에 대한 DP

다음으로 쿼리 x1 y1 x2 y2 에 대한 값을 구해야 한다.

예를 들어 쿼리 2,2,3,3 일 때 부분 행렬에 포함된 1의 개수 = DP [1][3][3] - DP [1][3][1] - DP [1][1][3] + DP [1][1][1]이다.

파란 영역을 빼주는 과정에서 겹치는 부분이 발생하기 때문에 마지막에 겹친 부부를 더 해준다.

이걸 식으로 바꿔보면  dp [number][x2][y2] - dp [number][x2][y1-1] - dp [number][x1-1][y2] + dp [number][x1-1][y1-1]이다.

식의 값이 0보다 크다면 개수를 하나 더 해주고 이 과정을 최대 정수 K까지 반복한다.

 

 

#include <iostream>
#include <vector>
#define MAXSIZE 300
using namespace std;

int board[MAXSIZE+1][MAXSIZE+1];
int dp[11][MAXSIZE+1][MAXSIZE+1];
int n, q, maxn;

int calc(int n, int x, int y){    
    int dx[3] = {-1, 0, -1};
    int dy[3] = {0, -1, -1};
    int result = 0;
    for(int i = 0; i < 2; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        result += dp[n][ny][nx];
    }
    result -= dp[n][y+dy[2]][x+dx[2]];
    return result;
}

void input(){
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> board[i][j];
            maxn = max(board[i][j], maxn);
        }
    }
}

void solve(){
    //set dp
    for(int i = 1; i <= maxn; i++){
        for(int y = 1; y <= n; y++){
            for(int x = 1; x <= n; x++){
                dp[i][y][x] = calc(i, x, y);
                dp[i][y][x] += board[y][x] == i;
            }
        }
    }
    int x1, y1, x2, y2;
    cin >> q;
    vector<int> answer;
    for(int i = 0; i < q; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        int sum = 0;
        for(int number = 1; number <= maxn; number++){
            sum += (dp[number][x2][y2] - dp[number][x2][y1-1] - dp[number][x1-1][y2] + dp[number][x1-1][y1-1]) > 0;
        }
        answer.push_back(sum);
    }

    for(auto i : answer){
        cout << i << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    input();
    solve();
}