[백준][Java] 11660번 구간 합 구하기 5 (누적합)

누적합 기믹만 알면 ㅈㄴ쉬움 진짜..

모든 알고리즘이 그러하듯..

파훼법을 아니까 왜 이런게 어렵게 느껴졌나 싶음

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        int M = stoi(str[1]);
        
        int[][] table = new int[N+1][N+1];
        int[][] preSum = new int[N+1][N+1];
        
        for(int i=1; i<=N; i++) {
            str = br.readLine().split(" ");
            for(int j=1; j<=N; j++) {
                table[i][j] = stoi(str[j-1]);
                preSum[i][j] = 
                        preSum[i-1][j] + preSum[i][j-1] 
                        - preSum[i-1][j-1] + table[i][j];
            }
        }
        
        for(int i=1; i<=M; i++) {
            str = br.readLine().split(" ");
            int x1 = stoi(str[0]);
            int y1 = stoi(str[1]);
            int x2 = stoi(str[2]);
            int y2 = stoi(str[3]);
            
            int res = 
                    preSum[x2][y2]
                    -preSum[x1-1][y2]-preSum[x2][y1-1]
                    +preSum[x1-1][y1-1];
            System.out.println(res);
        }
        
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}