[백준] 2167 2차원 배열의 합 - 2차원 누적합(Prefix Sum) JAVA

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

2167번: 2차원 배열의 합

코드설명

2차원 배열에 누적합을 활용하여 풀 수 있는 문제입니다.

 

처음에 문제를 보고, 단순히 for문을 사용하여 풀면 되지 않나 라고생각했지만,

문제 조건을 보면, 

• 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다.
• 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다.
• 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

배열의 크기 N, M은 최대 300 * 300 = 900,000 의 크기입니다.

합을 구할 부분의 개수는 최대 10,000 개입니다.

그리고 for문을 활용하여 풀경우, 최악의 경우 900,000 을 모두 도는 경우가 있습니다.

O(NM * K)  = 9,000,000,000 = 90억의 연산이 필요하므로 시간초과가 걸립니다.

 

누적합을 사용할경우,

처음에 누적합 배열을 구하는데에는 O(N*M)의 시간복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어듭니다.

 

1. 누적합배열을 구하기

for(int i=1;i<=N;i++) {
    for(int j=1;j<=M;j++) {
        prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
    }
}

• prefixSum[i][j] = 배열값 + 왼쪽 누적합 + 위쪽 누적합 - 교집합 누적합

 

2. 합연산 구하기

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

• 합연산 = 전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합

 

추가로, 누적합배열에 있어서 prefixSum[N][M] 이라고 가정할때, prefixSum[N][M]은 arr[0][0] ~ arr[N-1][M-1] 까지의 합이라는것을 인지해야합니다.

만약 prefixSum[1][1] 이라면, arr[0][0]  ~ arr[0][0] 까지의 합이 될 것 입니다.

 

주어진 입력의 누적합은, 아래와 같습니다.

0 0 0 0 
0 1 3 7 
0 9 27 63

코드

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

public class Main {
	public static int N, M, K;
	public static int[][] arr;
	public static int[][] prefixSum;
	public static long answer;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    		
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	arr = new int[N][M];
    	prefixSum = new int[N+1][M+1];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + arr[i-1][j-1]; 
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	K = Integer.parseInt(st.nextToken());
    	for(int t=0;t<K;t++) {
    		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());
    		
    		System.out.println(prefixSum[x][y] - prefixSum[i-1][y] - prefixSum[x][j-1] + prefixSum[i-1][j-1]);
    		
    	}
    	
    	
	}
}

 

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


public class Main {
	
	public static int N, M;
	public static int[][] arr;
	public static int[][] prefixSum;
	public static int K, i,j,x,y;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	arr = new int[N][M];
    	prefixSum = new int[N+1][M+1];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	K = Integer.parseInt(st.nextToken());
    	
    	for(int v=0;v<K;v++) {
    		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 = prefixSum[x][y] - prefixSum[x][j-1] - prefixSum[i-1][y] + prefixSum[i-1][j-1];
    		System.out.println(result);
    	}
    }
}