[Java] 백준 16507번 어두운 건 무서워

누적합 문제입니다.

직사각형안의 값들의 평균을 구하는 문제입니다.
(R * C) * Q =  (1000 * 1000) * 10000
=> 10_000_000_000이 나오므로 매번 모든 값들을 더하면 시간초과가 발생합니다.
 
2차원 배열의 누적합을 구해줍니다.
직사각형이 주어지면 해당 위치의 값을 누적합을 통해서 구하고 안의 개수만큼 나누어서 평균을 출력해줍니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int r = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());
    int[][] map = new int[r + 1][c + 1];
    int result = 0;

    for (int i = 1; i <= r; ++i) {
      st = new StringTokenizer(br.readLine());
      for (int j = 1; j <= c; ++j) {
        int num = Integer.parseInt(st.nextToken());
        map[i][j] = map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1] + num;
      }
    }

    for (int i = 0; i < q; ++i) {
      st = new StringTokenizer(br.readLine());
      int y1 = Integer.parseInt(st.nextToken());
      int x1 = Integer.parseInt(st.nextToken());
      int y2 = Integer.parseInt(st.nextToken());
      int x2 = Integer.parseInt(st.nextToken());
      int div = (y2 - y1 + 1) * (x2 - x1 + 1);

      result = (map[y2][x2] - map[y1 - 1][x2] - map[y2][x1 - 1] + map[y1 - 1][x1 - 1]) / div;
      bw.write(result + "\n");
    }

    bw.close();
  }
}