P.11660 구간 합 구하기 5

코드

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

public class P_11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = arr[0], m = arr[1];

        int[][] matrix = new int[n + 1][n + 1];
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            int[] board = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = board[j - 1];
                if (i > 0) dp[i][j] = dp[i - 1][j];
                for (int k = 0; k <= j; k++) dp[i][j] += matrix[i][k];
            }
        }

        for (int i = 0; i < m; i++) {
            int[] xy = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int y1 = xy[0], x1 = xy[1], y2 = xy[2], x2 = xy[3];

            int result = dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 -1][x1 - 1];
            bw.write(result + "\n");
        }
        bw.flush();
    }
}

코드 설명

dp로 구간의 모든 합을 저장해놓고 푸는 문제이다.

문제에서 제시된건 2차원 행렬이기 때문에 dp 또한 구간합을 행렬식으로 저장한다.

 

예제 1의 행렬의 경우 dp는 다음과 같은 모양을 띤다.

예를 들어, (2, 3)은 1 + 2 + 3 + 2 + 3 + 4 = 15이다.

좌측과 상단의 0은 편의상 dp의 인덱스를 1부터 했기 때문에 발생했다.

 

이제 주어진 x1, y1, x2, y2를 가지고 구간 합을 구하면 된다.

 

첫 예시로 (2, 2), (3, 4)가 주어졌다.

 

 

dp[3][4]는 위의 파란색 부분의 구간합을 가지고,

위 그림처럼 노란색 부분을 제거하면 (2, 2)~(3, 4)의 구간합이 나오게 된다.

 

그럼 위 노란색을 다시 쪼개보자.

주황색은 dp[3][1]이며, 빨간색은 dp[1][4]이다.

이 구간합을 제거하면 주황색과 빨간색이 겹치는 부분(위 그림에선 1)이 중복으로 제거되게 된다.

dp[1][1]을 다시 더해주기만 하면 된다.

 

좀 더 어려운 예제로 보자.

이 예제는 제거되어야 할 부분합이 dp[3][2]와 dp[1][4]이다.

그리고 중복으로 제거된 부분은 dp[1][2]다.

 

중복으로 제거된 부분을 어떻게 찾는지 슬슬 감이 올 거다.

주황색 부분이 dp[n][m], 빨간색 부분이 dp[x][y]일 때,

중복으로 제거된 부분은 dp[x][m]이 된다.

 

즉, 점화식은 다음과 같게 된다.

result = dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1]