No11660 구간합 구하기5

이번엔 1차원 배열을 이용한 구간합 구하기가 아니라 2차원 배열을 이용한 구간합 구하기에 대해서 알아볼 것이다.

2차원 배열 합 배열의 공식을 먼저 살펴보도록 하자.

먼저 기본적인 배열이 아래와 같이 주어져있다고 할 때, 이 배열의 합 배열을 직접 그려가면서 이해해볼 것이다.

회색 칸은 단순히 (0, 0)의 인덱스를 나타낸 것으로 전부 0이라고 생각하면 되고 흰색 칸의 값들이 들어가있다고 할 때 첫번째 행과 첫번째 열의 합부터 구해보면 1차원 배열의 합배열과 똑같은 것을 알 수 있다.

첫번째 열을 구하는 공식은 D[1][j-1] + A[1][j]이고 첫번째 열을 구하는 공식은 D[i-1][1] + A[i][1]이다.

행과 열이 섞여있어 헷갈릴 수 있는데 직접 그림은 그리면서 생각해보면 이해가 될 것이다.

그렇다면 첫번째 열과 행이 아니라 나머지 값들은 어떻게 구해줘야 할까?

(2,2)의 값을 구하려면 실제로 1 + 2 + 2 + 3 = 8이라는 값이 나와야 하는데 이 부분을 구하는 공식은

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]이다.

각각의 칸을 1 2

                  3 4   이라고 생각했을 때 실제 4번칸에 들어가야 하는 값은 1 + 2 + 3 + 4의 결과값인데 합배열을 생각해보면

(1 + 2) + (1 + 3) + 4의 결과값이 4에 들어가는 값일 텐데 1번 칸은 2번 더해졌으므로 1번 칸을 빼줘야 한다.

 

자, 이제 구간 합을 생각해보면 (2,2) ~ (3,4)의 구간합을 구하라는 문제가 주어졌을 때,

이러한 그림을 생각해볼 수 있다. 일단 전체 (3,4)의 범위에서 (1, 1~4)의 값을 제거하고 또 (1~3, 1)의 값을 제거하고 (1,1)이 2번 제거됐으므로 한번만 더해주면 (2,2) ~ (3,4)까지의 합만 남을 것이다. (X1, Y1) ~ (X2, Y2)라고 가정했을 때 공식은

D[X2, Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1,Y1-1]

 

 

[문제]

[입출력 및 조건]

 

[수도 코드]

• N : 배열의 사이즈 결정(N x N), M : 테스트 케이스
• 원본 배열 [N+1][N+1] 생성 후 안에 넣어줄 값들 받아오기 for(1~N)
• 합배열 D 생성 : D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]
• for(1~N) 구간합을 구할 범위 받아오기 : a1 b1 a2 b2
• 구간합 공식을 이용해서 결과값 도출 : D[a2, b2] - D[a1-1][b2] - D[a2][b1-1] + D[a1-1][b1-1]

 

[코드 작성]

public class Main {
    public static void main(String[] args) throws Exception{
        // N x N -> 배열의 크기, M -> 테스트 케이스
        // 배열의 크기에 따라 들어갈 값 받아오기
        // for문 1~N번
        // 2차원 합배열 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1]+A[i][j]
        // for문 M번 구간 범위 값 받아오기 -> D[X2-Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y-1]

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        //N x N
        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-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j];
            }
        }

        //구간합 구하기
        for(int i=0;i<M;i++) {
            int result = 0;
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken());
            int b2 = Integer.parseInt(st.nextToken());
            result = D[a2][b2] - D[a1-1][b2] - D[a2][b1-1] + D[a1-1][b1-1];
            System.out.println(result);
        }

        br.close();


    }
}

 

이번 문제는 처음에 2차원 배열을 이용해서 합배열을 만드는 공식을 이해하는데 시간이 오래걸렸고 실제 문제를 푸는건 기본 개념만 알고있으면 비교적 간단하게 풀 수 있는 문제였어서 푸는데 어려운 부분은 없었다. 이제 이 알고리즘을 이용해서 응용된 문제를 풀어본다면 많이 헷갈릴 수도 있을 것 같다. 내일은 구간합 알고리즘을 이용해서 좀 더 생각해야할 부분이 많은 문제를 풀어볼 예정이다.