[백준 11660] 구간 합 구하기 5 / 자바 / 누적합

문제         

레벨: 
알고리즘: 누적합
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

이 문제는 이차원배열의 누적합이다.

알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다.

 

혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다.  

---------
-->O

우린 1,1,를 좌상 꼭지점으로  O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.

합을 화살표 표시하고 그림으로 나타내면 아래와 같다

------ 
--->O

 

위 그림을 보면서 배열에 들어가는 값을 이해해보자.

빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다.

 

최종값 = 초록색 부분

x2 y2의 값은 빨간색부분의 원소를 모두 합한 값이다. 초록색 부분을 구하려면

빨간색 - 파란색 - 보란색 + 노란색(겹치는 부분)을 해주면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {

        // 1. N, M, N*N 배열 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());	// 2차원 배열의 크기
        int M = Integer.parseInt(st.nextToken());	// 구해야하는 구간 합의 수

        // 2. 배열 입력과 동시에 합배열 구하기
        // S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]
        int[][] S = new int[N+1][N+1];
        for(int i=1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<N+1; j++) {
                S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        // 3. 구간 합 구한 후 출력
        // 구간 합 = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
        int result = 0;
        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());
            result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
            System.out.println(result);
        }
    }
}