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

이번 문제는 dp, 누적합 문제이다.

    j→  1   2   3
    i↓ ┌──────────
    1  │ 1   2   3
    2  │ 4   5   6
    3  │ 7   8   9

이렇게 입력이 들어왔을 때

    j→  1   2   3
    i↓ ┌──────────
    1  │ 1   3   6
    2  │ 5  12  21
    3  │12  27  45

이런 누적합 배열로 저장해야 한다.

[2][2]를 예시로 들면1 + 2 + 4 + 5 = 12가 되고
[3][2] 는 1 + 2 + 4 + 5 + 7 + 8 = 27이 된다.

prefixSum[i][j] = arr[i][j]
                + prefixSum[i-1][j]
                + prefixSum[i][j-1]
                - prefixSum[i-1][j-1];

 

 

최종 코드는 아래와 같다.

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

public class Main {
    static int N, M, x1, y1, x2, y2, result;
    static int[][] arr, prefixSum;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][N+1];
        prefixSum = new int[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                prefixSum[i][j] = arr[i][j]
                        + prefixSum[i - 1][j]
                        + prefixSum[i][j - 1]
                        - prefixSum[i - 1][j - 1];

            }
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            result = 0;
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            int result = prefixSum[x2][y2]
                    - prefixSum[x1 - 1][y2]
                    - prefixSum[x2][y1 - 1]
                    + prefixSum[x1 -1][y1 - 1];

            System.out.println(result);
        }

    }

}