[JAVA] 백준 11660 누적합

11660번: 구간 합 구하기 5

문제

1차원 배열이 아닌 2차원 배열의 구간합을 구하는 문제이다.

풀이

단순히 2차원 배열로 확장한 것이 아니라 일정 4각형 범위의 구간합을 구하라는 문제이다.

다음과 같은 구간이 있다면 구간합 배열은 다음과 같다.

 

기존의 배열 A와 합배열 S가 있다면 다음과 같이 계산된다.

S[x][y] = S[x-1][y] + S[x][y-1] + A[x][y] - S[x-1][y-1]

이를 그림으로 나타내보면 다음과 같다.

S[2][2] = S[1][2] + S[2][1] + A[2][2] - S[1][1] = 3 + 3 + 3 - 1 = 8

다음과 같이 계산된다!

반대로 정해진 구간합을 구하기 위해서는 다음과 같은 수식으로 계산된다.

(2, 2) ~ (3, 4)의 구간합을 계산하려면

answer = S[3][4] - S[3][2 - 1] - S[2 - 1][4] + S[2 - 1][2 - 1]

answer = 42 - 6 - 10 + 1 = 27

그림으로 나타내면 다음과 같다.

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

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 size = Integer.parseInt(st.nextToken());
        int testcase = Integer.parseInt(st.nextToken());

        int[][] A = new int[size+1][size+1];
        int[][] D = new int[size+1][size+1];
        for(int i=1; i<=size; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1; j<=size; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1; i<=size; i++){
            for(int j=1; j<=size; j++){
                                // 구간 합 배열 생성
                D[i][j] = D[i][j-1] + D[i-1][j] + A[i][j] - D[i-1][j-1];
            }
        }

        for(int i=0; i<testcase; 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());
                        // 구간 합 배열을 이용해 계산
            System.out.println(D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]);
        }
    }
}

결과