백준_11660_구간합구하기5

https://www.acmicpc.net/problem/11660

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

class Main {
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int [][] dp = new int[N + 1][N + 1];

        // 입력을 받아 가로 줄 별로 구간 합 계산
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i][j - 1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();

        // M개 쿼리 처리
        for (int i = 0; i < M; i++) {
            int sum = 0;
            st = new StringTokenizer(bf.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());

            for (int j = x1; j <= x2; j++) {
                sum += dp[j][y2] - dp[j][y1 - 1]; // y1 도 포함되도록
            }
            sb.append(sum).append('\n');
        }
        // 결과 출력
        System.out.print(sb.toString());
    }
}

누적합 입력

• 각 줄의 값을 읽어서 dp 배열에 누적 합을 계산하면서 저장.
• dp[i][j]에는 (i, j) 위치까지의 가로 방향 합이 저장.

누적합 계산

• (x1,y1) ~ (x2,y2) 조건 : x1 <= x2 , y1 <= y2
• dp[x1][y2] - dp[x1][y1-1] 이걸 x1...x2까지 반복