[백준/Java] 11660번 구간 합 구하기 5

-Code

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

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

        int size = Integer.parseInt(st.nextToken());
        int testCase = Integer.parseInt(st.nextToken());
        // 표 셋팅 (col을 누적합으로 계산)
        int[][] graph = new int[size + 1][size + 1];
        for (int row = 1; row <= size; row++) {
            st =  new StringTokenizer(br.readLine());
            for (int col = 1; col <= size; col++) {
                int input = Integer.parseInt(st.nextToken());
                graph[row][col] = graph[row][col - 1] + input;
            }
        }
        // row를 기준으로 다시 누적합 계산
        for (int row = 1; row <= size; row++) {
            for (int col = 1; col <= size ; col++) {
                graph[row][col] += graph[row - 1][col];
            }
        }
        // 계산
        for (int t = 0; t < testCase; t++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            // 값을 구하려면 세로와 가로줄을 잘라내야함
            int total = graph[x2][y2];
            int cutRow = graph[x2][y1 - 1];
            int cutCol = graph[x1 - 1][y2];
            // 세로 가로를 잘라낸 후 겹치는 부분은 2번 빠지므로 더해줘야함
            int overLap = graph[x1 - 1][y1 - 1];

            System.out.println(total - cutRow - cutCol + overLap);
        }
    }
}

dp 구성을 잘해놓았으나 1차원 누적합으로 값을 구하는 문제처럼 (마지막 점 - 시작 점)으로 결과를 구했다가 다른 값이 나왔습니다. 그래서 왜 이런지 찾아보니 그렇게 구하는 게 아니라 전체 값에서 세로와 가로를 잘라내고 겹치는 부분을 다시 더해주는 공식이어서 공식을 알게 된 뒤 해결하게 되었습니다.