[BOJ] 11660번 구간 합 구하기 5 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, M;
    static int[][] arr, sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N + 1][N + 1];
        sum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                sum[i][j] = arr[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        for (int i = 0; i < M; i++) {
            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 result = sum[x2][y2] - (sum[x2][y1 - 1] + sum[x1 - 1][y2]) + sum[x1 - 1][y1 - 1];
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

📄 해설

• 2차원 누적합의 기본문제. 2차원 누적합에서의 핵심을 파악해야 풀 수 있다.

2차원 누적합의 핵심?

• 앞선 문제인 1차원 누적합의 경우는 단순히 바로 직전 값을 더해주기만 하면 되었음
• 그러나 2차원 누적합의 경우, 위와 같이 계산을 하게 되면 그냥 1차원 누적합을 여러개 구한 것과 다를게 없어짐
• 2차원 누적합의 경우는, 현재 위치의 값, 왼쪽까지의 누적합, 대각선 왼쪽 위까지의 누적합, 위쪽까지의 누적합을 활용하여 구해야하며, 원본 배열을 arr, 누적합 배열을 sum 이라고 할 때, 이를 코드로 표현하면 다음과 같음
  sum[i][j] = arr[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
  앞서 언급했듯, 현재 위치의 값, 왼쪽까지의 누적합, 위쪽까지의 누적합을 더하고, 대각선 왼쪽 위 까지의 누적합을 빼서 구함
  • 대각선 왼쪽 위의 누적합(sum[i-1][j-1])을 빼는 이유는 그림을 그려서 확인해보면 굉장히 쉽게 알 수 있음.
  • 아래의 그림을 보자(그림은 작성자의 똥손 이슈로 인해 다른 블로그의 그림으로 대체하였음.)
    출처 : https://chanhuiseok.github.io/posts/baek-19/
    
    
    
• 위와 같이 그림을 그려보게 되면, 대각선 위쪽의 값이 중복되어 계산됨을 확인할 수 있음
• 이제 누적합을 다 구했으므로, 구간합을 구할 차례 구간합은 아래와 같은 과정으로 구하게 되며, 그림을 같이 첨부하였음
  • ($x_2, y_2$) 의 누적합 - ($x_1-1, y_2$의 누적합 + $x_2, y_1-1$의 누적합) + $(x_1-1, y_1-1)$의 누적합
    
• 본 문제가 이해가 되지 않는다면, 그림을 그려가면서 하는 것을 추천함