[백준, 자바, 11660번] 구간 합 구하기 5

풀이

• 어제 구간 합 유형 문제를 풀어서 그런지
• 해결 방법이 쉽게 떠올랐음
• 단순히 2차원 배열을 그냥 하나의 배열의 묶음으로 생각하고 
• 각 배열을 누적하여 합한 다음
• 원하는 구간의 합을 구하여 해결
• 아래 주석은 배열 2개로
• 기존 입력 값을 담은 배열과, 누적 합을 구한 배열 두개로 한 거고
• 주석이 없는 코드는 하나의 배열로 해결한 코드

 

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

public class _11660 {
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        StringTokenizer st = new StringTokenizer(br.readLine());
//        int N = Integer.parseInt(st.nextToken());
//        int M = Integer.parseInt(st.nextToken());
//        long[][] mtx = new long[N][N];
//        long[][] check = new long[N+1][N+1];
//        for (int i=0; i<N; i++) {
//            st = new StringTokenizer(br.readLine());
//            for (int j=0; j<N; j++) {
//                mtx[i][j]=Integer.parseInt(st.nextToken());
//                check[i+1][j+1]=check[i+1][j]+mtx[i][j];
//            }
//        }
//
//        while (M>0) {
//            st = new StringTokenizer(br.readLine());
//            int x1 = Integer.parseInt(st.nextToken());
//            int y1 = Integer.parseInt(st.nextToken());
//            int x2 = Integer.parseInt(st.nextToken());
//            int y2 = Integer.parseInt(st.nextToken());
//            long hap = 0L;
//            for (int i=x1; i<=x2; i++) hap+=check[i][y2]-check[i][y1-1];
//            bw.write(hap+"\n");
//            M--;
//        }
//        bw.flush();
//    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[][] mtx = new long[N][N+1];
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<=N; j++) {
                mtx[i][j]=Integer.parseInt(st.nextToken())+mtx[i][j-1];
            }
        }
        while (M>0) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            long hap = 0L;
            for (int i=x1-1; i<x2; i++) hap+=mtx[i][y2]-mtx[i][y1-1];
            bw.write(hap+"\n");
            M--;
        }
        bw.flush();
    }
}