[AJ/DP] 직사각형의 합

문제

N x M 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.

 

입력

첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형이 주어진다. 직사각형 안의 숫자 S는 -100이상 100이하이다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다. (0 ≤ a ≤ c < N, 0 ≤ b ≤ d < M)  

출력

각 질문에 대한 답을 출력한다.

 

예제 입력

5 5 3 1 -2 3 2 8 -8 -9 3 4 5 2 4 7 8 2 1 4 3 1 4 -1 2 5 -6 3 1 2 3 4 0 0 1 1 2 0 2 1

예제 출력

37 -18 6

---

풀이

입력 받을 때 area[][]에 0,0 기준으로 입력받은 좌표까지의 면적을 계산하여 저장한다.

입력받는 값이 다음과 같을 때

1	2	3
4	5	6
7	8	9

area[][]에 저장되는 값은 다음과 같다.

1	3	6
5	12	21
12	27	45

 

0,0 부터 a,b의 면적을 구할 때는 area[a][b]를 출력하면 된다.

 

하지만 (0,0)이 아닐 때는 그 전에 더했던 면적을 빼야한다.

 

예를 들어 (1,1) 부터 (2,2)의 면적일 경우

area[0][2] 는 1+2+3 이다.

area[2][0] 은 1+3+7 이다.

즉, area[2][2] - area[2][0]-area[0][2]+area[0][0] 이다.

(여기서 area[0][0]은 중복으로 두 번 빠지기 때문에 한 번 더해야 한다.)

1	3	6
5	12	21
12	27	45

 

따라서 다음과 같은 점화식을 갖는다.

 

if (a == 0 && b == 0)  area[c][d]; 
else if (a > 0 && b > 0) area[c][d] - area[c][b-1] - area[a - 1][d] + area[a - 1][b - 1]; 
else if (a == 0)  area[c][d] - area[c][b-1]; 
else if (b == 0)  area[c][d] - area[a-1][d];

코드

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        long area[][] = new long[n][m];

        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < m; j++) {
                sum += sc.nextLong();
                if (i > 0)
                    area[i][j] = sum + area[i - 1][j];
                else
                    area[i][j] = sum;
            }
        }

        for (int i = 0; i < q; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int d = sc.nextInt();
            long sum = 0;
            if (a == 0 && b == 0)
                sum = area[c][d];
            else if (a > 0 && b > 0)
                sum = area[c][d] - area[c][b-1] - area[a - 1][d] + area[a - 1][b - 1];
            else if (a == 0)
                sum = area[c][d] - area[c][b-1];
            else if (b == 0)
                sum = area[c][d] - area[a-1][d];

            System.out.println(sum);

        }
    }

}​