문제

접근

단순히 더하면 시간초과가 뜬다. dp를 사용하자.

x축 오른쪽방향으로 누적합을 더하는 dp 매트릭스를 만든다.
X1일때 Sum X1 = 큰 y의 누적합 - 작은 y보다 작은 범위=(y1-1)의 누적합
X2일때 Sum X2 = 큰 y의 누적합 - 작은 y보다 작은 범위=(y1-1)의 누적합

Xn의 sum을 구하면 범위 안의 sum을 구할 수 있다.

성공 코드

package B_DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(r.readLine());
        int N = Integer.parseInt(st1.nextToken());
        int loop= Integer.parseInt(st1.nextToken());

        int [][]dp = new int[N+1][N+1];


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

        while(loop-->0){
            int sum =0;

            int[] read = Arrays.stream(r.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int x1 = read[0];
            int y1 = read[1];
            int x2 = read[2];
            int y2 = read[3];

            for (int i = x1; i <= x2; i++) {
                sum = sum + (dp[i][y2] - dp[i][y1-1]);
            }
            System.out.println(sum);
            sum=0;
        }


    }
}