백준[JAVA] - 2차원 배열의 합 (2167)

---

이번 문제는 2차원 배열을 활용할줄만 알면 쉽게 풀 수 있는 문제였다!

 

package S5_Baekjoon;

import java.util.*;

public class Baekjoon2167 {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);  
        int N = sc.nextInt();  // 배열의 행 수 입력
        int M = sc.nextInt();  // 배열의 열 수 입력

        int[][] vec = new int[N][M];  // N x M 크기의 2차원 배열 생성

        // 2차원 배열에 값 입력
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                vec[i][j] = sc.nextInt();
            }
        }

        int K = sc.nextInt();  // 쿼리의 개수 입력
        int i,j,x,y;
        for(int s = 0; s < K; s++){
            // 쿼리 범위 입력 (1-indexed를 0-indexed로 바꾸기 위해 -1)
            i = sc.nextInt() - 1;  
            j = sc.nextInt() - 1;  
            x = sc.nextInt() - 1;  
            y = sc.nextInt() - 1;  
            int answer = 0;

            // 쿼리 범위 내의 배열 요소를 모두 더함
            for(int f = i; f <= x; f++){
                for(int a = j; a <= y;  a++){
                     answer += vec[f][a];
                }
            }
            System.out.println(answer);  
        }
    }
}

 

이 문제에 대해서 더 알아본 결과 나처럼 푸는 것도 있지만 더  빠른 시간복잡도를 가진 방법으로도 풀 수 있었다 그건 "누적 합"을 이용해서 풀면 됬다.

 

누적 합 이란 배열의 시작부터 현재 위치까지의 모든 합을 말한것이다

 

누적 합을 사용하면 O(1)의 시간복잡도로 구할 수 있다.

 

누적 합을 미리 계산해 놓으면 임의의 사격형 영역의 합 (i,j)부터 (x,y)까지의 합을 구할 수 있다.

dp[i][j] = arr[i][j] + dp[i -1][j] + dp[i][j -1] - dp[i-1][j-1] 

sum = dp[x][y] - dp[i-1][y] -dp[x][j-1] + dp[i-1][j-1]

 

 

누적합 배열의 원리에 대해서 이해하기 어려워서 찾아봤다

 

예시로 

a  b
c  d

2 X 2 배열이 있다면

 

각 위치의 누적합 값은 원래 배열에서 (1,1) 위치부터 해당 위치까지의 모든 원소의 합이다

a            a+b
a+c       a+b+c+d

이 누적합 배열을 어떻게 사용하냐면

 

누적 합 배열의 (i , j)위치의 값은 원래 배열의 (i , j)위치의 값과 누적합 배열의 (i-1 , j)위치의 값, 그리고 (i , j-1)위치의 값에서 (i-1, j-1)위치의 값을 빼는 것과 같다.

이렇게 하는 이유는 (i -1, j)와 (i, j-1)를 더 하면 (i -1 , j-1)위치의 값이 두번 더해지기 때문이다

 

숫자로 예시를 들자면

1  2  3
4  5  6
7  8  9

이런식으로 2차원 배열이 있을 때

 

누적합 배열은 

1   3   6
5  12  21
12 27  45

이런식으로  정해지게 된다

 

그럼

dp[i][j] = arr[i][j] + dp[i -1][j] + dp[i][j -1] - dp[i-1][j-1] 

dp[2][2] (12)를 구하기 위해선 = arr[2][2] (5) + dp[1][2] (3)+ dp[2][1] (5)- dp[1][1] (1)

 

이렇게 된다

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 배열의 행과 열 크기를 입력 받습니다.
        int N = sc.nextInt();
        int M = sc.nextInt();

        // 입력 값을 저장할 배열과 누적 합을 저장할 배열을 선언합니다.
        int[][] arr = new int[N+1][M+1];
        int[][] dp = new int[N+1][M+1];

        // 입력 값을 배열에 저장합니다.
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        // 누적 합 배열을 생성합니다. 
        // dp[i][j]는 (1,1)에서 (i,j)까지의 모든 원소의 합입니다.
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                dp[i][j] = arr[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }

        // 쿼리의 수를 입력받습니다.
        int K = sc.nextInt();
        while(K-- > 0) {
            // 쿼리의 시작점(i, j)과 끝점(x, y)을 입력 받습니다.
            int i = sc.nextInt();
            int j = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            // (i, j)에서 (x, y)까지의 구간합을 계산합니다.
            // 구간합 = 전체합 - 위쪽 구간합 - 왼쪽 구간합 + 겹치는 구간합
            int answer = dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1];
            System.out.println(answer);
        }
    }
}