[JAVA] 백준 구간 합 구하기 5

누적해서 합을 구한 값을 배열에 넣고

각 시행마다의 덧셈을 최소화 시키는 방식을 선택했다.

오른쪽으로 한칸씩 더해지는 방식

위 방식대로 하면 효율성이 좋은 코드가 나올 수 있다.

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

public class Main {
    static int N, M;
    static int[][] grid;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        grid = new int[N][N];
    /*
    case1 : (14-2) + (18-3) = 12 + 15 = 27
    누적합(가로)
    1 3 6 10
    2 5 9 14
    3 7 12 18
    4 9 15 22
    */
        StringBuilder sb= new StringBuilder();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if(j>0) grid[i][j] += grid[i][j-1];
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int r1 =  Integer.parseInt(st.nextToken())-1;
            int c1 =  Integer.parseInt(st.nextToken())-1;
            int r2 =  Integer.parseInt(st.nextToken())-1;
            int c2 =  Integer.parseInt(st.nextToken())-1;
            int sum=0;
            for(int r=r1; r<=r2; r++){
                if(c1>0) sum += (grid[r][c2] - grid[r][c1-1]);
                else sum += grid[r][c2];
            }

           sb.append(sum).append('\n');
        }
        System.out.print(sb.toString());
    }
}