[실전 문제] 직사각형의 합

1. 문제

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

 

 

 

2. 풀이

이 문제의 아이디어는 간단하다. 입력 받을 때 (0,0) 기준으로 입력받은 좌표까지의 면적을 합산하여 저장하면 된다.

 

3 x 3 입력값이 들어왔을 때의 예시는 다음과 같다.

 

합산된 배열에서는 (0,0)을 기준으로 계산했기 때문에, (0,0)부터 (1,1)까지의 정수의 합은 합산된 배열의 (1,1)이 된다.

(1,1)부터 (2,2)까지의 정수의 합은 다음과 같다.

이러한 특징을 이용하여 코드를 작성해주면 된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());


        long[][] arr = new long[n][m];
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long sum = 0L;
            for(int j = 0; j < m; j++) {
                sum += Integer.parseInt(st.nextToken());
                if(i > 0) arr[i][j] = sum + arr[i-1][j];
                else arr[i][j] = sum;
            }
        }

        for(int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            long sum = 0L;
            if(a == 0 && b == 0) sum = arr[c][d];
            else if(a > 0 && b > 0) {
                sum = arr[c][d] - arr[c][b-1] - arr[a-1][d] + arr[a-1][b-1];
            } else if(a == 0) {
                sum = arr[c][d] - arr[c][b-1];
            } else if(b == 0) {
                sum = arr[c][d] - arr[a-1][d];
            }

            bw.write(sum + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

}