[백준] 16507 어두운 건 무서워 - 2차원 누적합(2차원 Prefix Sum) JAVA

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

16507번: 어두운 건 무서워

코드설명

누적합을 사용할경우,

처음에 누적합 배열을 구하는데에는 O(N*N)의 시간복잡도가 주어지지만, 합을 구하는 연산이 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];

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

 

코드

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

public class Main {
	public static int R, C, Q;
	public static int[][] arr;
	public static int[][] prefixSum;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	

    	R = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	Q = Integer.parseInt(st.nextToken());
    	
    	prefixSum = new int[R+1][C+1];
    	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());
    		}
    	}
    	
    	for(int i=1;i<=R;i++) {
    		for(int j=1;j<=C;j++) {
    			prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] + arr[i-1][j-1] - prefixSum[i-1][j-1];
    		}
    	}
    	
    	
    	for(int i=0;i<Q;i++) {
        	st = new StringTokenizer(br.readLine());
        	int r1 = Integer.parseInt(st.nextToken());
        	int c1 = Integer.parseInt(st.nextToken());
        	int r2 = Integer.parseInt(st.nextToken());
        	int c2 = Integer.parseInt(st.nextToken());
        	
        	int value = prefixSum[r2][c2] - prefixSum[r2][c1-1] - prefixSum[r1-1][c2] +prefixSum[r1-1][c1-1];
        	int answer = value / ((r2 - r1 + 1) * (c2 - c1 + 1));
        	System.out.println(answer);    		
    	}

    	
    }
}