[JAVA]BOJ 11660, 구간 합 구하기 5

누적 합을 이용하는 문제이다. 처음에는 모든 숫자들의 합을 구했는데.. 그게아니라 (1,1)부터 (i,j)까지의 합을 미리 구하는 방식이더라. 

 

1. 입력받아 arr[][] 배열을 만든다.

2. 누적합 배열 acc[][] 배열을 만든다.

3. 누적합을 바탕으로 (x1,y1)부터 (x2,y2)의 합을 구한다.

 

크게 이렇게 정리할 수 있다..

 

1. 입력받아서 arr[][] 배열 만들기

쉬우니까 생략.. 전체코드 참고하세요

 

2. 누적합 배열 acc[][] 배열을 만든다.

음.. 우선 나는 배열을 [0]부터 쓰지않고 [1]부터 썼다. 문제에서 0으로 시작하지 않았고 배열 경계선(?)에 주는 조건을 더 간단히 할 수 있기 때문이다.

 

    [0] ...    [4]

[0] 0 0 0 0 0
     0 1 2 3 4
     0 2 3 4 5
     0 3 4 5 6
[4] 0 4 5 6 7

arr[4][4] 예시, 위와 같이 구현했다.

 

누적합을 구하는 방식은 아래와 같다.

acc[2][2]를 구하는 방식을 그림으로 그려봤다. (1,1)부터 현재자리까지의 합을 구하기위해서 위, 아래의 합에 중복되는 부분을 빼면 된다. 그리고 마지막에 현재자리의 값을 더한다. 식으로 표현하면 아래와 같다.

   acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + arr[i][j];

 

인덱스를 1부터 시작했기 때문에 상단 또는 제일 우측라인(경계선)에 대해 예외처리를 하지 않아도 된다. 어쩌피 0이니까.. 아래 표에서 굵게 표시된 부분을 말하는거다.

    [0] ...    [4]

[0] 0 0 0 0 0
     0 1 2 3 4
     0 2 3 4 5
     0 3 4 5 6
[4] 0 4 5 6 7

// 누적합 구하기
for(i=1;i<=N;i++){
    for(j=1;j<=N;j++){
            acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + arr[i][j];
    }
}

 

3. 누적합을 바탕으로 (x1,y1)부터 (x2,y2)의 합을 구한다.

이것도 먼저 그림으로 표현해봤다.

빗금처리된 사각형이 (x1,y1)과 (x2,y2)의 합을 표현한거고 구해야 할 값이다. 우리는 (1,1)부터 (i,j)의 합을 미리 다 구해놨으므로 그 합을 이용해 부분합을 구할 수 있다!

전체 큰 사각형 그림에서 빗금쳐진 부분을 제외하고 빼면 빗금친 부분만 남을것이다. 이를 식으로 표현하면

'(x2,y2)의 합 - (x1-1,y2) 의 합 - (x2,y1-1) 의 합 + (x1-1,y1-1) 의 합' 이 된다. 엉성하지만 그림으로 표현하자면.. 아래와 같다..ㅋㅋ

위에 직사각형 1개, 우측에 직사각형 1개 빼고 빗금 부분을 1번 더해준다. 빗금부분이 두 번 빠지기 때문이다..

예시 몇 개 해서 풀어보면 바로 이해가 될거다.

// x1, y1, x2, y2 입력
for(i=0;i<M;i++){
    str = br.readLine();
    st = new StringTokenizer(str);

    x1 = Integer.parseInt(st.nextToken());
    y1 = Integer.parseInt(st.nextToken());
    x2 = Integer.parseInt(st.nextToken());
    y2 = Integer.parseInt(st.nextToken());

    System.out.println(acc[x2][y2] - (acc[x1 - 1][y2] + acc[x2][y1 - 1]) + acc[x1 - 1][y1 - 1]);
}

 

---

아래는 전체 코드이다.

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

public class BOJ11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, i, j, x1, y1, x2, y2;
        int[][] arr;
        int[][] acc;
        String str;
        StringTokenizer st;


        str = br.readLine();
        st = new StringTokenizer(str);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][N+1];
        acc = new int[N+1][N+1];

        // arr배열 만들기
        for(i=1;i<=N;i++){
            str = br.readLine();
            st = new StringTokenizer(str);
            for(j=1;j<=N;j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }

        // 누적합 구하기
        for(i=1;i<=N;i++){
            for(j=1;j<=N;j++){
                    acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + arr[i][j];
            }
        }

        // x1, y1, x2, y2 입력
        for(i=0;i<M;i++){
            str = br.readLine();
            st = new StringTokenizer(str);

            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            System.out.println(acc[x2][y2] - (acc[x1 - 1][y2] + acc[x2][y1 - 1]) + acc[x1 - 1][y1 - 1]);
        }
    }
}