[java] 11660 구간합 구하기 5

1. 문제 링크 및 문제

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

1-1 문제 요약

:(x1,y1) ~ (x2,y2) 합을 구함

2. 해결 방법 생각해보자 ...

누적합 방식 이용

3. 코드

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

public class Main {

    static int N,M;
    static int[][] arr;
    static int[][] sumArr;
    static int[] xy = new int[4];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        sumArr = new int[N+1][N+1];

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

        // 배열합 구하기 -->
        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] - sumArr[i-1][j-1] + arr[i-1][j-1];
            }
        }
        // <--

        // 들어온 좌표값 계산 
        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 ans = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1];
            System.out.println(ans);
        }
        
    }
}

이해해보자

int ans = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1]; 설명

arr, sumArr의 현재 형태

구해야 하는 것 (백준 예시 1) 2,2 부터 3,4까지의 합

1. sumArr[x2][y2] =sumArr[3][4] 로, arr에서 0,0~3,4까지의 합
   

2. sumArr[x1-1][y2] = sumArr[1][4]로, arr에서 0,0~0,4 까지의 합
   

3. sumArr[x2][y1-1] = sumArr[3][1]로, arr에서 0,0~3,0 까지의 합
   

1,2,3 을 모두 표에 나타내보면
42에, 6과 10을 빼면 2,2~3,4 까지의 합을 얻을 수 있다!,근데 1이 두 번 빼지므로, + sumArr[x1-1][y1-1] 해주는 것.
( 42에, 6과 10을 == 연파랑에, 찐파랑과 나무색을)