백준 [JAVA] 2167. 2차원 배열의 합

일정한 규칙이 존재한다.

우선 문제와 같이 2차원 배열을 이용해 순차적으로 값을 더해준다.

 

예를 들어 주어진 값이 아래와 같다면

1	2	3
4	5	6
7	8	9

순차적으로 더한 배열의 값은 아래와 같을 것이다.

1	3	6
5	12	24
12	27	45

 

위의 계산을 편하게 하기 위해 나는 여분의 배열 0행과 0열을 주었다.

즉,

0	0	0	0
0	1	3	6
0	5	12	24
0	12	27	45

 

와 같은 결과 행렬이 될 것이다.

해당 배열[x][y] 위치의 값은 [x][y] = [x][y] + [x-1][y] + [x][y-1] - [x-1][y-1] 이다.

해당 배열 위치의 자신의 값에 위와 왼쪽 값을 더하고 이중 중복되는 왼쪽 위방향의 대각선 방향의 배열 값[x-1][y-1]을 빼준다.

 

 

이제 해당 범위 값인 결과값을 계산하는 방법이다.

파란 영역이 구할 값의 영역이라면 3번 배열의 위치에서 2번의 위치 배열을 빼고 1번 배열을 더해준다.

위와 비슷한 방식으로 1은 2번 빼주게 되기 때문에 1을 더해주는 것이다.

집합의 교집합 연산과 같은 방식이다. 

 

 

아래의 코드가 위의 방식을 이용한 풀이이다.

 

 

package algo;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B_2167_2차원배열의합 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken()) + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }
        int K = Integer.parseInt(in.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            sb.append((arr[x][y] - arr[a - 1][y] - arr[x][b - 1] + arr[a - 1][b - 1]) + "\n"); // 여기
        }
        System.out.println(sb);
    }
}