[백준] 14846 직사각형과 쿼리 - JAVA

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

14846번: 직사각형과 쿼리

 

 

알고리즘

• 누적합 알고리즘으로 접근하여 풀기 
• dp[a][b][c] : (1,1) ~ (a,b) 부분 행렬에 포함되어 있는 정수 c의 갯수 (1 ≤ c ≤ 10) 
• 특정 위치(a,b)에서 각 정수의 누적 갯수 : dp[a][b][c] = dp[a][b-1][c] + dp[a-1][b][c] - dp[a-1][b-1][c] 
• (a1,b1)~(a2,b2) 를 기준으로 부분행렬을 만들었을 때 : dp[a2][b2][c] - dp[a2][b1-1][c] - dp[a1-1][b2][c] + dp[a1-1][b1-1][c]

---

소스 코드

import java.util.*;
import java.io.*;

public class BaekJoon_Solution_14846 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N= Integer.parseInt(br.readLine());
		int[][][] dp = new int[N+1][N+1][11]; //특정 위치에 번호가 몇개 있는지 (번호는 1~10의 자연수) 
		
		StringTokenizer st; 
		int num=0; 
		for(int a=1; a<=N; a++) {
			st= new StringTokenizer(br.readLine(), " "); 
			for(int b=1; b<=N; b++) {
				for(int c=1; c<=10; c++) {
					dp[a][b][c] = dp[a-1][b][c]+dp[a][b-1][c]-dp[a-1][b-1][c]; 
				}
				num = Integer.parseInt(st.nextToken());//해당 위치 의 번호 
				dp[a][b][num]++;  
			}
		}
		
		int Q= Integer.parseInt(br.readLine()); 
		while(Q-- >0) {
			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 cnt=0; 
			for(int i=1; i<=10; i++) {
				if((dp[x2][y2][i]-dp[x2][y1-1][i]-dp[x1-1][y2][i]+dp[x1-1][y1-1][i]) >0 ) cnt++;
			}
			System.out.println(cnt);
		}
	}//end of main 
}//end of class