백준 14846번 : 직사각형과 쿼리

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)

 

 

 

 

 

풀이

 (x1, y1)~(x2, y2)인 부분 행렬에서 서로 다른 정수의 개수를 구하는 문제로, (x1, y1)~(x2, y2)인 부분 행렬에서 누적합을 구하는 문제와 비슷하다.

 

백준 11660번 구간 합 구하기5 : https://www.acmicpc.net/problem/11660)

(풀이) 백준 11660번 구간 합 구하기5 : https://programmingiraffe.tistory.com/160

 

 

 

 

 

• 다이나믹 프로그래밍

 처음 생각할 수 있는 풀이는 (x1, y1)~(x2, y2)까지 모두 탐색하며, 각 정수가 몇 개 나왔는지 세는 것이다. 하지만 문제의 입력을 살펴보면, 행렬 크기인 N이 최대 300, 쿼리의 개수인 Q가 최대 100,000으로 매번 부분 행렬을 모두 탐색한다면, 최악의 경우 O(N^2 * Q) = 300 * 300 * 100,000는 약 90억의 시간이 걸린다.

 

 따라서 연산의 횟수를 줄이기 위해, 앞에 각 정수가 몇 개 나왔는지를 활용하여 현재까지의 각 정수의 개수를 구할 수 있는 DP를 활용해야 한다.

 

 

 

• (1, 1)~(i, j)까지의 각 정수 개수 구하기

 

(i, j)까지의 각 정수 개수를 저장할 DP 배열을 3차원으로 선언해준다. 

int[][][] dp = new int[11][N + 1][N + 1];

 

 

그리고 모든 좌표를 순회하고, 1~10 모든 숫자에 대해 (i, j)까지의 해당 숫자의 개수를 DP로 계산을 한다.

 

 

 

 어떤 숫자 num의 (i, j)까지의 개수는 빨간색 부분인 dp[num][i - 1][j]와 파란색 부분인 dp[num][i][j - 1]를 더하고, 중복해서 더한 노란색 부분인 dp[num][i - 1][j - 1]을 빼준 것이다. 만약 arr[i][j]의 값이 어떤 숫자인 num과 같다면 +1을 해주면 된다.

 

 

 

• (x1, y1)부터 (x2, y2)까지의 각 원소의 개수 구하기 

(x1, y1)~(x2, y2)의 어떤 정수의 개수를 구하는 데는 (1, 1)~(i, j)까지의 어떤 정수의 개수인 dp[num][i][j]를 활용하여 적절히 연산을 하면 된다.

 

 

 노란색 부분을 구하기 위해서는 초록색 부분인 dp[num][x1 - 1][y2]를 빼고, 파란색 부분인 dp[num][x2][y1 - 1]을 빼주고, 중복해서 뺀 부분인 회색 부분인 dp[num][x1 - 1][y1 - 1] 을 더해주면 된다.

 

 

 

• 1~10의 dp[num][i][j] 확인하기

 문제에서 제시된 정수의 범위인 1~10의 DP를 모두 확인하며, 0이상이라면 해당 숫자가 있으므로 정답의 개수를 증가시켜주면 된다.

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); //행렬 크기
		
		int[][] A = new int[N + 1][N + 1]; //행렬
		
		for(int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j = 1; j <= N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][][] dp = new int[11][N + 1][N + 1]; //행렬 (i, j)까지의 해당 번호의 개수
		
		//행렬 (i, j)까지의 각 번호별 개수 구하기
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				for(int k = 1; k <= 10; k++) {
					dp[k][i][j] = dp[k][i - 1][j] + dp[k][i][j - 1] - dp[k][i - 1][j - 1];
				}
				dp[A[i][j]][i][j]++;
			}
		}
		
		int Q = Integer.parseInt(br.readLine()); //쿼리 수
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < Q; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int answer = 0;
			for(int num = 1; num <= 10; num++) {
				int count = dp[num][x2][y2] - dp[num][x1 - 1][y2] - dp[num][x2][y1 - 1] + dp[num][x1 - 1][y1 - 1];
			
				if(count > 0) answer++;
			}
			sb.append(answer).append("\n");
		}
		
		System.out.println(sb);
	}

}

 

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 3차원 DP 배열로 (i, j)까지의 해당 숫자의 개수를 저장