어두운 건 무서워 - 16507번

---

풀이 방법

처음에 반복문을 통해 풀이했는데 시간초과가 나왔다. 사진크기가 1000*1000이고 Q가 10000이 된다면 1000 * 1000 * 10000번 연산하게 되어 제한시간이 초과되는 것으로 보인다. 

prefix sum 방법을 사용해서 풀이 했다. 배열의 (0,0) 부터 (x,y) 까지의 합을 우선 구해두고 계산할 때 꺼내 쓰는 방식이다. 

 

내 코드

package com.company;

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


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 R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        int[][] array = new int[R + 1][C + 1];

        for (int i = 1; i < R + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < C + 1; j++) {
                array[i][j] = array[i - 1][j] + array[i][j - 1] - array[i - 1][j - 1] + Integer.parseInt(st.nextToken());
            }
        }


        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int r2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int sum = array[r2][c2] - array[r1 - 1][c2] - array[r2][c1 - 1] + array[r1 - 1][c1 - 1];
            System.out.println(sum / ((r2 - r1 + 1) * (c2 - c1 + 1)));
        }

    }
}