2167 2차원 배열의 합 JAVA

 

이번 문제는 간단한 2차원 배열의 누적합을 구현하는 문제이다.

이 문제를 구간 합 구하기라는 문제에서 구현해본 적이 있지만 복습할 겸 다시 풀어보았다.

 

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

 

우선 기본적인 수를 입력 받는 방법이나 변수 선언, 누적합 기본 로직에 대해선 언급하지 않을 예정이다.

 

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

public class P2167 {
    static int[][] matrix;
    static int[][] prefixSum;
    public static void main(String[] args) throws IOException {
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        matrix = new int[n][m]; prefixSum = new int[n+1][m+1];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < m; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
                prefixSum[i+1][j+1] = prefixSum[i][j+1] + prefixSum[i+1][j]
                        - prefixSum[i][j] + matrix[i][j];
            }
        }

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int y1 = Integer.parseInt(st.nextToken()), x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken()), x2 = Integer.parseInt(st.nextToken());

            sb.append(calPrefixSum(y1,x1,y2,x2)+"\n");
        }
        System.out.println(sb);
    }
    public static int calPrefixSum(int y1, int x1, int y2, int x2) {
        return prefixSum[y2][x2] - prefixSum[y2][x1-1] - prefixSum[y1-1][x2]
                + prefixSum[y1-1][x1-1];
    }
}

 

입력값의 크기가 매우 크기 때문에, 누적합을 구현하지 않고는 이 문제는 왠만해서 시간초과가 날것이다.

또한 누적합을 구한다면 이런 값들을 간단하게 구할 수 있다.

 

그럼 어떻게 구현할 수 있는지, 테이블을 그리면서 설명을 해보도록 하겠다.

입력 예시는 백준 입력 예시와 동일하게 예를 들겠다.

이 배열의 이름은 matrix

1	2	4
8	16	32

위와 같이 수를 입력했을 때, 누적합 배열의 각 배열엔 아래와 같은 값이 들어와야 한다. 

이 배열의 이름은 presumFix

0	0	0	0
0	1	3	7
0	9	27	63

이게 이해가 안된다면 누적합의 기본 원리에 대해 복습하는 것을 추천한다.

 

아무튼, 이렇게 우리가 머리로 계산을 하면 이런식으로 계산이 된다는건 초등학교 덧셈 산술만 할줄 알면 누구나 할 수 있다.

하지만 어떻게 컴퓨터가 알아들을 수 있도록, 코드를 작성할 수 있을까와는 별개의 문제이다.

 

먼저 우리가 2차원 구간에 대한 합을 빠르게 구하기 위해선, presumFix를 먼저 초기화 하여야 한다.

 

로직은 이렇다.

예를 들어 matrix (1,1) = 1;  matrix(1,2) = 3; matrix(1,3) = 7;인데 여기엔 규칙이 하나 있다.

 

구하려는 presumFix 배열 기준으로 바로 왼쪽 값과 바로 윗쪽 값을 더하고, 중복된 대각선 값을 차감한 후, 마지막으로 현재 위치의 matrix 값을 더하면 모든 presumFix를 구할 수 있다. 

 

이게 뭔말이냐 하면, presumFix 배열의 [2][2] 를 구해보겠다.

나 자신의 왼쪽값 9와 윗쪽값 3을 더한 후, 중복된 대각선 값 1을 뺀 후, matrix(2,2)의 값인 16을 더하면

presumFix[2][2] = 9 + 3 - 1 + 16;  

presumFix[2][2] = 27;

이게 가능한 이유는 도형의 넓이라고 생각하면 된다.

 

따라서 이렇게 초기화를 진행하고, 실제 특정 구간의 값을 구할 땐 이 로직을 써서 계산하면 된다.