[백준] 2167번 : 2차원 배열의 합 (JAVA)

📌 문제 링크

https://www.acmicpc.net/problem/2167

---

📌 문제 개요

N × M 크기의 2차원 배열이 주어진다.

이후 K개의 질의가 주어지며 각 질의는 다음과 같다.

 

(i, j) ~ (x, y)

 

해당 범위에 포함되는 모든 배열 값의 합을 구하는 문제

---

📌 접근 방법

매번 범위를 직접 탐색하면 시간 복잡도가 커질 수 있다.

그래서 행 기준 누적합(Prefix Sum)을 이용

 

각 행에서 왼쪽부터 누적합을 저장하면 특정 구간 합을 **O(1)**에 계산할 수 있다.

 

예를 들어 한 행에서

1 2 4
// 누적합 : 1 3 7

 

이때 구간 (2 ~ 3)의 합은 prefix\[3\] - prefix\[1\] 로 계산할 수 있다.

---

📌 핵심 아이디어

행 누적합 공식 : prefix\[i\]\[j\] = prefix\[i\]\[j-1\] + arr\[i\]\[j\]

 

구간 (j ~ y) 합 : prefix\[row\]\[y\] - prefix\[row\]\[j-1\]

 

전체 영역 : (i,j) ~ (x,y)

for(row = i ~ x)  
sum += prefix\[row\]\[y\] - prefix\[row\]\[j-1\]

 

단, j가 첫 열일 경우 prefix\[row\]\[y\] 만 사용

---

📌 전체 코드

package no_2167;

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

public class No2167 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[][] arr = new int[r][c];

        for(int i = 0; i < r; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < c; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] prefix = new int[r][c];

        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(j == 0){
                    prefix[i][j] = arr[i][j];
                }else{
                    prefix[i][j] = prefix[i][j-1] + arr[i][j];
                }
            }
        }

        int k = Integer.parseInt(br.readLine());

        for(int t = 0; t < k; t++){

            st = new StringTokenizer(br.readLine());

            int i = Integer.parseInt(st.nextToken()) - 1;
            int j = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            int sum = 0;

            for(int row = i; row <= x; row++){

                if(j == 0){
                    sum += prefix[row][y];
                }else{
                    sum += prefix[row][y] - prefix[row][j-1];
                }

            }

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

---

📌 정리

이 문제는 2차원 누적합의 기본 개념을 이해하는 문제

행 기준 누적합을 사용하면

 

시간복잡도 : O(N\*M + K\*N) 으로 해결할 수 있다.