15724 주지수

1. 풀이

 

누적 합을 이용한다.

 

예제를 가지고 설명하겠다.

 

4 4
9 14 29 7
1 31 6 13
21 26 40 16
8 38 11 23
3
1 1 3 2
1 1 1 4
1 1 4 4

 

 

 

1) sum 배열

 

sum[i][j] = sum[i][j-1] + (i,j) 위치에 살고 있는 사람 수 

로 채운다. 

 

즉, 

 

9       23(9+14)       52(23+29)    59(52+7)

1       32(1+31)       38(32+6)      51(38+13)

 

이런 식으로 채운다.

 

<sum 배열>

 

 

sum 배열의 (1,1) 위치 값은 9 이다.

즉 sum[1][1] = 9

 

 

 

2) dp 배열

 

dp[i][j] = (1,1) 부터 (i,j) 까지의 인구수 합

 

=> dp[i][j] = dp[i-1][j] + sum[i][j]

 

 

즉,

 

<dp 배열>

 

 

3) 결과 출력

 

 

주어진 직사각형 범위의 (x1,y1) ~ (x2,y2) 의 사람 수 합은

 

dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] 로 구하면 된다.

 

즉, 문제 예제에 주어진

(1,1) ~ (3,2) 를 구할 때는

dp[3][2] - dp[3][0] - dp[0][2] + dp[0][0] 

 

=> dp[1][1] = 9 이고,

0행, 0열은 0으로 채워져 있다.

 

따라서 dp[3][2] = 102 이므로

102 - 0 - 0 + 0 = 102 가 답이 된다.

 

 

 

 

2. 최종 코드

 

 

 

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));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int sum[][] = new int[N+1][M+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " " );
			for(int j=1; j<=M; j++) {
				sum[i][j] = sum[i][j-1] +  Integer.parseInt(st.nextToken());
			}
		}
		
	
		int dp[][] = new int[N+1][M+1];
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				dp[i][j] = dp[i-1][j] + sum[i][j];
			}
		}
		
		int K = Integer.parseInt(br.readLine());
		
		for(int i=0; i<K;i++ ) {
			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 result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
			System.out.println(result);
	  }
	}
}