[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());
​​​​}
}