문제

이해

NxN 크기의 표에 숫자가 각각 공간에 채워져 있다.

표 상에서 두 점의 좌표를 입력받고 해당 좌표의 구간 합을 구해야 한다.

좌표는 (x1, y1) (x2, y2)로 주어지며 x1과 y1은 각각 x2, y2보다 작거나 같다.

위 그림은 (2, 2) ~ (3, 4)까지의 구간 합을 구해야할때 포함되는 범위를 나타낸 것이다.

접근

주어진 조건을 보자. N은 1024이하 자연수이고 M은 100,000이하 자연수이다.

이 때문에 주어진 좌표를 보고 구간합을 일일이 더하기는 시간상으로 불가능해 보인다.

따라서, 누적합을 이용하기로 한다.

2차원 평면상에서 누적합을 어떻게 나타내면 좋을까?

그것은 특정 좌표를 기준으로 (0, 0)부터 (x, y)까지의 누적합으로 설정하면 사용하기 용이할 것으로 보인다.

그렇다면 누적합은 어떻게 저장할 수 있을까? 여기서는 다이나믹 프로그래밍이 사용된다.

왜냐하면 이전 좌표에서 구했던 누적합이 이후에 구할 누적합에 사용되기 때문이다. 메모이제이션을 활용하면 되겠다.

구체적인 방법을 보자. (x1, y1)에서의 누적합을 구할려고 할때, 우선 우리가 알고있는 정보로는

1. (x1, y1) 이전 좌표의 누적합 (구하는 순서는 일반적인 이차원배열 탐색 순서와 같음)
2. (x1, y1) 에서의 입력값

가 있다.

이를 통해 (x1, y1)에서의 누적합은 다음과 같이 나타낼 수 있다.

위 그림은 (3, 3)에서의 누적합을 구할 때의 그림이다.

(3, 3) 누적합 = (2, 3) 누적합 + 3행 1열 ~ 2열 합 + 입력값

으로 정리할 수 있는데 이를 통해 점화식은 다음과 같이 세울 수 있다.

(x1, y1) 누적합 = (x1 - 1, y1) 누적합 + x1행 1열 ~ y1-1 열 합 + 입력값

위의 점화식으로 (1, 1)부터 (N, N)까지의 모든 누적합을 구할 수 있다.

그렇다면 특정 좌표 사이의 구간합은 어떻게 구하면 될까?

얻은 큰 좌표의 누적합에서 제외해야 하는 부분을 단순하게 빼면 된다. 이를 그림으로 나타내면 다음과 같다.

예제대로 (2, 2) ~ (3, 4)의 구간합을 구하는 그림이다.

구간합 = (3, 4) 누적합 - (3, 1) 누적합 - (1, 4) 누적합 + (1, 1) 누적합

(1, 1)은 겹치는 부분이기 때문에 더해준다.

이를 식으로 나타내면 다음과 같다.

(x1, y1) ~ (x2, y2) 구간합 = (x2, y2) 누적합 - (x2, y1-1) 누적합 - (x1-1, y2) 누적합 + (x1-1, y1-1) 누적합

코드

package java_baekjoon;

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

public class prob11660 {
    static int N;
    static int M;
    static int x1, x2, y1, y2;
    static int[][] square;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        square = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int row_sum = 0;

            for (int j = 1; j <= N; j++) {
                row_sum += Integer.parseInt(st.nextToken());
                square[i][j] = square[i - 1][j] + row_sum;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

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

            int ans = square[x2][y2] - square[x2][y1 - 1] - square[x1 - 1][y2] + square[x1 - 1][y1 - 1];

            System.out.println(ans);
        }
    }
}

과정이 조금 복잡해보이지만 점화식을 세우고 이를 코드로 정확하게 구현하기만 하면 쉬운 문제이다.

결과