백준 11660 번 : 구간 합 구하기 5 (Java)

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

Key Point

1. (x1,y1) 부터 (x2, y2) 까지의 구역의 합을 구하는 문제이다.

2. 2차원 배열 dp에 1,1 부터 (x,y) 까지의 합을 기억해놓는다.

 

1 2 3 4

2 3 4 5

 

인 경우, dp 는

1 3 6 10

3 7 14 24

 

이다.

 

3. x1 <= x2이고 y1 <= y2 이므로, (x1,y1) 부터 (x2,y2) 까지의 합은, 

1,1에서 x2,y2 까지의 합(큰 사각형) 빼기

1,1에서 x1,y2 까지의 합 빼기

1,1에서 x2,y1 까지의 합 더하기

1,1에서 x1,y1 까지의 합이다. (이 부분은 두번 마이너스 됐기 때문이다.)

 

이것만 알면 구현은 쉽다.

 

소스코드

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N, M;
    static int[][] map, dp;
    static Op[] ops;

    static class Op {
        int x1;
        int y1;
        int x2;
        int y2;

        public Op(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }

    static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        map = new int[N+1][N+1];
        dp = new int[N+1][N+1];
        ops = new Op[M];
        for(int i = 1 ; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 1 ; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j];
                //x1,y1 부터 x2,y2 까지의 합을 구하는 로직과 동일하게 dp를 구한다.
            }
        }
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            ops[i] = new Op(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
    }

    static void solve() {
        for(int i = 0 ; i < M; i++) {
            Op op = ops[i];
            System.out.println(dp[op.x2][op.y2] - dp[op.x2][op.y1-1] - dp[op.x1-1][op.y2] + dp[op.x1-1][op.y1-1]);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}