[Boj_2167] 2차원 배열의 합

문제 설명

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

 

▸ 문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

 

▸ 입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

 

▸ 출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 5
• 🔔  문제 유형 : 구현, 누적합
• 💬  풀이 언어 : Java

 

문제 풀이

문제를 풀기 전, 먼저 누적합(Prefix Sum)에 대해 알아보자.

 

🔍 누적합(Prefix Sum)

누적합이란, 배열의 일부 구간에 대한 합을 빠르게 구하기 위해 이전까지의 합을 미리 저장해두는 알고리즘이다.

배열의 값이 변하지 않는 한, 누적합도 변하지 않으므로 한 번 계산해두면 특정 구간의 부분합을 O(1)에 구할 수 있다.

이처럼 값을 미리 저장해 재활용한다는 점에서 누적합은 동적 계획법(DP)과 유사한 개념이다.

 

이제 문제를 해결하기 위해 입력으로 주어진 2차원 배열에 대해 누적합 배열(prefix)을 생성한 뒤, 각 위치까지의 누적합을 미리 계산해 저장한다.

 

누적합 배열은 다음 점화식을 이용해 계산한다.

prefix[i][j] = map[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];

• 이는 현재 위치의 값 map[i][j]에
• 왼쪽 누적합 prefix[i-1][j],
• 오른쪽 누적합 prefix[i][j-1]을 더하고,
• 중복된 영역인 prefix[i-1][j-1]을 한 번 빼주는 방식이다.

 

이후 (i, j)부터 (x, y)까지의 부분합은 다음 점화식으로 구할  수 있다.

sum = prefix[x][y] - prefix[i-1][y] - prefix[x][j-1] + prefix[i-1][j-1];

• 이는 전체구간(prefix[x][y])에서
• 왼쪽 영역과 위쪽 영역을 제외하고,
• 두 번 빠진 교집합 영역(prefix[i-1][j-1])을 다시 더해주는 방식이다.

 

이 과정을 통해 모든 질의에 대해 빠르게 부분합을 계산할 수 있다.

 

코드

메모리 : 26240 KB 
시간 : 276 ms

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        
        int[][] map = new int[n+1][m+1];
        int[][] prefix = new int[n+1][m+1]; // 누적합을 저장할 배열
        
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 누적합 구하기
                prefix[i][j] = map[i][j] + prefix[i-1][j] + prefix[i][j-1]
                               - prefix[i-1][j-1];
            }
        }
        
        int k = Integer.parseInt(br.readLine()); // 질의 개수
        while (k --> 0) {
            st = new StringTokenizer(br.readLine());
            // (i, j) 위치부터 (x, y) 위치
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // ans : (i, j) 위치부터 (x, y) 위치까지의 합
            // 점화식 : 전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합
            int ans = prefix[x][y] - prefix[i-1][y] - prefix[x][j-1] + prefix[i-1][j-1];
            
            bw.append(ans + "\n");
        }
        
        bw.flush();
        
        bw.close();
        br.close();
    }
}