배열의 구간 합 2 - 2차원 배열의 구간 합 구하기

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

220928

11660번: 구간 합 구하기 5

package day1.bj_11660;
import java.util.*;
import java.io.*;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int A[][] = 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++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int D[][] = new int[N+1][N+1];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                D[i][j] = D[i][j-1] +D[i-1][j]-D[i-1][j-1]+A[i][j];
            }
        }

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.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());

            int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1]+D[x1-1][y1-1];
            System.out.println(result);
        }
    }
}

2차원 배열의 구간합 sum을 작성하여 해결한다.

sum[i][j] = 네모(sum[1][1] ~ sum[i][j])의 구간 합을 나타냄