[백준] BOJ_11660 - 구간 합 구하기 5

1. 문제 정보

• 문제 요약: $N \times N$ 크기의 표에 수가 채워져 있습니다. $(x_1, y_1)$에서 $(x_2, y_2)$까지의 직사각형 범위 내에 있는 수들의 합을 구하는 프로그램을 작성해야 합니다. (총 $M$번의 질의)
  
• 핵심 제약 조건:
  • 표의 크기 $N$: 최대 $1,024$
    
  • 합을 구해야 하는 횟수 $M$: 최대 $100,000$
    
  • 시간 제한: 1초
    
• 난이도: Silver I
  
• 링크: https://www.acmicpc.net/problem/11660
  

---

2. 접근 방식

1) 문제의 본질 분석

가장 먼저 떠오르는 방법은 질의가 들어올 때마다 이중 반복문을 통해 범위를 순회하며 더하는 것입니다. 하지만 이 방식의 시간 복잡도를 계산해 봅시다.

• 최악의 경우 하나의 질의를 처리하는 데 $O(N^2)$이 걸립니다.
  
• 질의가 $M$번 주어지므로 총 시간 복잡도는 $O(M \times N^2)$입니다.
  
• $100,000 \times 1024^2 \approx 10^{11}$번의 연산이 필요하며, 이는 1초(약 $10^8$번 연산)를 훌쩍 넘겨 시간 초과(TLE)가 발생합니다.
  

따라서, 우리는 질의(Query)가 들어올 때마다 $O(1)$에 답을 낼 수 있는 전처리(Pre-computation) 과정이 필요합니다. 이때 사용하는 알고리즘이 바로 2차원 누적 합(2D Prefix Sum)입니다.

2) 알고리즘 설계: 포함-배제 의 원리

2차원 배열에서 누적 합을 구하거나 특정 구간의 합을 구할 때는 집합의 포함-배제의 원리(Inclusion-Exclusion Principle)와 유사한 기하학적 아이디어를 사용합니다.

1. 누적 합 배열 생성 (dp[i][j]): $(1, 1)$부터 $(i, j)$까지의 사각형 영역 전체 합을 미리 구해둡니다.
2. 구간 합 계산: 우리가 원하는 $(x_1, y_1) \sim (x_2, y_2)$ 영역의 합은, 전체 큰 사각형에서 필요 없는 위쪽 영역과 왼쪽 영역을 빼고, 두 번 빠진 중복 영역(왼쪽 대각선 위)을 다시 더해주면 됩니다.

3) 점화식 및 수식

Step 1: 누적 합 배열 채우기

현재 위치 $(i, j)$까지의 누적 합은 [위쪽 누적 합] + [왼쪽 누적 합] - [대각선 위 중복 영역] + [현재 값]입니다.

$DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i][j]$

Step 2: 정답 도출하기

$(x_1, y_1)$부터 $(x_2, y_2)$까지의 부분 합은 다음과 같습니다.

$Answer = DP[x_2][y_2] - DP[x_1-1][y_2] - DP[x_2][y_1-1] + DP[x_1-1][y_1-1]$

---

3. 코드 구현

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] A = 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++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // DP 테이블 선언
        int[][] dp = new int[N + 1][N + 1];
        
        // 1. 첫 행과 첫 열 초기화 (Boundary Condition)
        for (int i = 1; i <= N; i++) {
            dp[i][1] = dp[i - 1][1] + A[i][1];
            dp[1][i] = dp[1][i - 1] + A[1][i];
        }

        // 2. 나머지 DP 테이블 채우기 (점화식 적용)
        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= N; j++) {
                dp[i][j] = A[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }

        StringBuilder sb = new StringBuilder();
        // 3. 쿼리 처리 (M번)
        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 answer = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            sb.append(answer).append('\n');
        }

        System.out.println(sb);
    }
}

---

4. 회고 및 배운 점

1) 시간 복잡도 비교

• Naive Approach: $O(M \times N^2)$ $\rightarrow$ 시간 초과
  
• DP (Prefix Sum):
  • 배열 구성: $O(N^2)$ (한 번만 수행)
    
  • 쿼리 처리: $O(1)$ (M번 수행)
    
  • 총 합계: $O(N^2 + M)$ $\rightarrow$ 통과