[백준 11660] 구간 합 구하기 5 (Java)

🚀 문제 핵심

1차원 구간 합의 확장판입니다. $N \times N$ 행렬이 주어질 때, $(x1, y1)$부터 $(x2, y2)$까지의 사각형 영역 안에 있는 수들의 합을 구해야 합니다. 이번에도 질의(M)가 10만 개이므로, 매번 더하면 무조건 시간 초과가 발생합니다.

---

💡 핵심 원리: 2차원 누적 합 (Prefix Sum 2D)

2차원 공간에서의 누적 합은 '포함-배제의 원리'를 이용합니다.

1. 합 배열 $S$ 만들기
   $S[i][j]$는 $(1, 1)$부터 $(i, j)$까지의 사각형 영역 합입니다.

• 공식: $S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + \text{현재값}$
• 중복해서 더해진 $S[i-1][j-1]$ 영역을 한 번 빼주는 것이 포인트입니다.

2. 구간 합(영역 합) 구하기
   $(x1, y1)$부터 $(x2, y2)$까지의 합은 전체 사각형($S[x2][y2]$)에서 필요 없는 위쪽과 왼쪽 영역을 도려내면 됩니다.

• 공식: $res = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]$
• 이때 두 번 빠진 왼쪽 위 모서리($S[x1-1][y1-1]$)를 다시 한 번 더해줍니다.

---

🧐 설계 포인트: 왜 이번에는 int인가?

지난번 1차원 구간 합에서는 습관적으로 long을 추천했지만, 이번에는 문제 조건을 보고 자료형을 최적화했습니다.

• 조건: $N \le 1,024$, 원소 값 $\le 1,000$
• 최대 합 계산: $1024 \times 1024 \times 1000 \approx 1,048,576,000$ (약 10억)
• Java의 int 최대 범위는 약 21억($2^{31}-1$)입니다.
• 결론: 누적 합의 최대치가 int 범위를 넘지 않음이 보장되므로, 메모리 효율을 위해 int[][]를 사용했습니다.

---

💻 구현 코드 (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        // try-with-resources로 리소스 자동 관리
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 1. 2차원 합 배열 구성
            int[][] S = 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++) {
                    // 포함-배제의 원리 적용
                    S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + Integer.parseInt(st.nextToken());
                }
            }

            // 2. 질의 처리
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < m; c++) {
                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 res = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];
                sb.append(res).append("\n");
            }

            bw.append(sb).flush();
        }
    }
}

---

🎯 정리

2차원 구간 합 문제는 수식을 정확히 유도하는 능력과 데이터 범위를 파악해 적절한 자료형을 선택하는 능력을 동시에 요구합니다. $N=1024$ 수준의 2차원 배열을 다룰 때는 S[i-1][j-1] 같은 인덱스 에러가 나지 않도록 배열 크기를 N+1로 잡는 디테일이 매우 중요합니다.