[ 누적합 ] 백준 - 2차원 배열의 합

 

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

 

풀이과정

누적합을 사용해보자!

 

물론 for문 써도 되는데 문제 조건이 헤비함

• 배열의 크기 N, M(1 ≤ N, M ≤ 300)
• 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)

 최악의 경우 300x300 크기의 배열에 K가 10,000개 이면

연산을 300*300*10,000번 해야됨. 에바잖슴

 

그래서 누적합을 써야된다!

 

누적합 배열을 처음에 생성할때 시간복잡도는 O( N * M )

합을 구할때에는 O( K )이다.

 

그래서 누적합을 사용하면 최종 시간복잡도는 O( N * M + K )가 된다

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int K = Integer.parseInt(br.readLine());
		
        //합 구하기
        for (int q = 0; q < K; q++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

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

             System.out.println(result);
        }

       
    }
}

 

코드 풀이

prefixSum[i][j] = array[i][j] 
                + prefixSum[i - 1][j] 
                + prefixSum[i][j - 1] 
                - prefixSum[i - 1][j - 1];

prefixSum[i][j] 의 값은 (0,0) 부터 ( i, j )까지의 값들의 합이므로

이전 prefixSum 을 더해주고, 중복값인 애들을 빼주면 됨.ㅇㅇ

 

result = prefixSum[x][y] 
       - prefixSum[x][j - 1] 
       - prefixSum[i - 1][y] 
       + prefixSum[i - 1][j - 1];

얘도 비슷하게 값 더해주고 중복값을 빼주면 damn