[문제풀이] B11660 구간 합 구하기 5

구간 합 구하기 5

---

  🪅 이차원배열에서의 누적합을 구할 수 있느냐
  🪅 누적합 배열을 만들 때, 패딩을 넣을 생각을 했느냐
  🪅 답을 구하는 규칙을 만들 수 있느냐 => int res = accTable[x2][y2] - accTable[x2][y1-1] - accTable[x1-1][y2] + accTable[x1-1][y1-1];

💡 문제 접근 과정
: 누적합을 이용해서 구간합을 구할 때는, 큰누적합- 작은누적합을 생각해야하고
 항상 누적합의 시작점은 같아야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 백준 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)까지 합을 구해 출력한다.
 *
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(token.nextToken()); // 4
        int M = Integer.parseInt(token.nextToken()); // 3
        int[][] table = new int[N+1][N+1]; // 패딩 행/열도 포함
        int[][] accTable = new int[N+1][N+1];

        // 1 ~ N번째 줄의 수 채우기
//           0 1 2 3 4
//           ---------
//           0 0 0 0 0
//           0 1 2 3 4
//           0 2 3 4 5
//           0 3 4 5 6
//           0 4 5 6 7
        for(int i = 1; i < N+1; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            for(int j = 1; j < N+1; j++) {
                table[i][j] = Integer.parseInt(token.nextToken());
            }
        }
//        System.out.println(Arrays.deepToString(table));

        // 누적합구하기
        for(int i = 1; i < N+1; i++) {
            for(int j = 1; j < N+1; j++) {
                accTable[i][j] = accTable[i-1][j] + accTable[i][j-1] - accTable[i-1][j-1] + table[i][j];
            }
        }
//        System.out.println(Arrays.deepToString(accTable));

        // M번, x1 y1 x2 y2 입력
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            int x1 = Integer.parseInt(token.nextToken()); // 2
            int y1 = Integer.parseInt(token.nextToken()); // 2
            int x2 = Integer.parseInt(token.nextToken()); // 3
            int y2 = Integer.parseInt(token.nextToken()); // 4
            int res = accTable[x2][y2] - accTable[x2][y1-1] - accTable[x1-1][y2] + accTable[x1-1][y1-1];
            System.out.println(res);
        }
    }
}