문제 설명

N×N 크기의 2차원 배열이 주어질 때,
다음 쿼리를 처리하는 문제이다.

(x1, y1) ~ (x2, y2) 구간의 합

즉, 2차원 영역의 합을 빠르게 구해야 한다.

---

입력

첫째 줄

N M

• N : 배열 크기
• M : 쿼리 개수

다음 N줄

N×N 배열

다음 M줄

x1 y1 x2 y2

조건

1 ≤ N ≤ 1024
1 ≤ M ≤ 100000

---

출력

각 쿼리마다 구간 합 출력

---

입력 예시

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

출력 예시

27
6
64

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

2차원 누적합(prefix sum)

---

왜 필요한가

내 코드처럼 매번 직접 계산하면

한 쿼리 = O(N)
전체 = O(N × M)

최대

1024 × 100000 ≈ 1억

→ 시간초과 발생

---

내가 작성한 코드

나는 1차원 누적합처럼 처리한 뒤
행 단위로 반복해서 합을 계산했다.

코드

import java.util.*;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int [] nums = new int[N*N+1];
        int sum = 0;

        for(int i = 1; i <= N*N; i++) {
            sum += sc.nextInt();
            nums[i] = sum;
        }

        for(int i = 0; i < M; i++) {

            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            int result = 0;

            for(int j = x1; j <= x2; j++) {
                result += nums[N*(j-1)+y2] - nums[N*(j-1)+y1-1];
            }

            System.out.println(result);
        }
    }
}

---

강의 코드

강의에서는 2차원 누적합 배열을 사용했다.

코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

class Main
{
    public static void main (String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[][] arr = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                arr[i][j] = sc.nextInt();

        int[][] acc = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                acc[i][j] = acc[i - 1][j]
                          + acc[i][j - 1]
                          - acc[i - 1][j - 1]
                          + arr[i][j];

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (M-- > 0) {

            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            bw.write(acc[x2][y2]
                   - acc[x1 - 1][y2]
                   - acc[x2][y1 - 1]
                   + acc[x1 - 1][y1 - 1] + "\n");
        }

        bw.flush();
    }
}

---

내 코드 vs 강의 코드 비교

1. 접근 방식 차이

내 코드

1차원 누적합 + 행 반복

→ 구간마다 반복문 필요

---

강의 코드

2차원 누적합

→ 한 번에 계산

---

핵심 차이

방식	특징
내 코드	쿼리마다 반복문 필요
강의 코드	O(1) 계산

---

2. 시간복잡도 차이

내 코드

O(N × M)

→ 시간초과

---

강의 코드

O(N² + M)

→ 통과

---

3. 핵심 공식 차이

내 코드

행마다 합 계산

---

강의 코드

acc[x2][y2]
- acc[x1-1][y2]
- acc[x2][y1-1]
+ acc[x1-1][y1-1]

→ 2차원 누적합 공식

---

핵심 개념

1. 2차원 누적합

acc[i][j] = 위 + 왼쪽 - 겹친부분 + 현재값

---

2. 구간 합 공식

(x1,y1) ~ (x2,y2)
= 전체 - 위 - 왼쪽 + 겹친부분

---

3. 왜 2차원이 필요한가

1차원 → 선
2차원 → 면

---

시간 복잡도

방식	복잡도
내 코드	O(N × M)
강의 코드	O(N² + M)

---

정리

이 문제는 단순 누적합 문제가 아니라
2차원 누적합 문제였다.

내 코드는 1차원 방식으로 접근해서
쿼리마다 반복문이 필요해 시간초과가 발생했다.

강의 코드는

2차원 누적합

을 사용하여 한 번의 계산으로 해결했다.

핵심 차이는 다음과 같다.

내 코드   → 반복 계산
강의 코드 → 공식 계산

즉, 이 문제는

2차원 누적합 공식을 알고 있는가

가 핵심인 문제였다.