백준 11660. 구간 합 구하기5

문제 11660. 구간 합 구하기5

문제

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 <= N <= 1024, 1 <= M <= 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 <= x2, y1 <= y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

풀이

arr 배열을 입력받았다고 했을때 누적합 배열은 다음과 같다.

(1,1) (2,1)까지의 누적합은 arr의 (1,1) + (2,1)의 값과 같다.
(2,2) (3,3)까지의 누적합은 arr의 (2,2) + (2,3) + (3,2) + (3,3)

누적합 (2,2)의 값은 arr의 (1,1) + (1,2) + (2,1) + (2,2) 와 같지만 매번 이런 방식으로 누적합을 구하게 되면 tle가 발생할 것이다.

누적합을 활용하여 누적합 배열을 생성하도록 한다.
ex) sum[2][2] = sum[2][1] + sum[1][2] - sum[1][1] + arr[2][2]다.

sum[2][1] = sum[1][1] + arr[2][1]
sum[1][2] = sum[1][1] + arr[1][2] 이므로
sum[1][1]이 두번 더해져서 sum[1][1]을 마지막에 한번 제거해주었다.

그래서 sum배열을 생성할때 sum[i][j]의 i or j 가 1일때를 처리해주기 위하여 sum배열의 크기를 arr의 크기와 같게하지 않고 n+1의 크기로 생성해주었다.

누적합 배열까지 생성하였다. 그러면 이제 해를 구하기 위한 방법을 알아보자.

입력 받은 x1, y1, x2, y2 가 (2,2) (3,2)인 경우이다.
이 값을 구하기 위해서는

(3,2) 까지의 누적합 sum[3][2]에서 sum[2][2]의 아래의 값과 sum[3][2]의 좌측값들을 빼주면 된다.

이 경우에도 sum[3-1][2-1]은 두번 제거되니 마지막에 한번 더해주도록 한다.

즉 x1, y1 = (a,b)
x2, y2 = (i,j)
answer = sum[i][j] - sum[a-1][j] - sum[i][b-1] + sum[a-1][b-1]

풀이코드 자바

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

public class boj11660 {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        int[][] sum = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j-1] - sum[i - 1][j - 1] + arr[i - 1][j - 1];
            }
        }



        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(stk.nextToken());
            int y1 = Integer.parseInt(stk.nextToken());
            int x2 = Integer.parseInt(stk.nextToken());
            int y2 = Integer.parseInt(stk.nextToken());

            sb.append(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1 - 1] + "\n");

        }

        System.out.println(sb.toString());

    }
}