[백준 11660] Java 구간 합 구하기 5 / 2차원 구간 합 배열

 

💙2차원 구간 합 배열 저장

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

>문제에서의 답 = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

 

[수도코드]

표의 크기 n, 함 구해야 하는 횟수 m 입력받기

for(n만큼 반복){

    for(n만큼 반복){

    표 채워넣을 수 입력받기 > 2차 a 배열에 저장

}}

for(n만큼 반복){

    for(n만큼 반복){

   구간 합 배열 저장 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

}}

for(m만큼 반복){

x1, y1, x2, y2 입력받기

D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1] 출력하기

}

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        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 k = 1; k <=m; k++){
            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);
        }
}
}