[백준] 11660 구간 합 구하기 5 - 누적합(2차원, (Prefix Sum)) JAVA

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

11660번: 구간 합 구하기 5

코드설명

2차원 배열의 누적합 문제입니다.

 

 

누적합을 사용할경우,

처음에 누적합 배열을 구하는데에는 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];

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

 

문제에서 유의해야할점은.,

prefixSum[N][N]은 arr[N-1][N-1] 까지의 합을 의미한다는 점입니다.

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

 

즉, 인덱스가 1칸씩 큰 값이 prefixSum으로 주어집니다.

이는 prefixSum을 구할때 범위문제가 발생하지 않게하는데 도움이 됩니다.

 

예로들어, prefixSum[2][1] 이라함은, arr[0][0] ~ arr[1][0]  까지의 합을 나타냅니다.

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

 

코드

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 int answer = 0;
    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][N];
    	prefixSum = new int[N+1][N+1];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] =Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=N;j++) {
    			prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
    		}
    	}
    	
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int x1 = Integer.parseInt(st.nextToken());
    		int y1 = Integer.parseInt(st.nextToken());
    		int x2 = Integer.parseInt(st.nextToken());
    		int y2 = Integer.parseInt(st.nextToken());
    		System.out.println(prefixSum[x2][y2] - prefixSum[x2][y1 - 1] - prefixSum[x1-1][y2] + prefixSum[x1-1][y1-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 sumValue = 0;
    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][N];
    	prefixSum = new int[N+1][N+1];
    	
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<N+1;i++) {
    		for(int j=1;j<N+1;j++) {
    			prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
//    			System.out.print(" "+prefixSum[i][j]);
    		}
//    		System.out.println();
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int x1 = Integer.parseInt(st.nextToken());
    		int y1 = Integer.parseInt(st.nextToken());
    		int x2 = Integer.parseInt(st.nextToken());
    		int y2 = Integer.parseInt(st.nextToken());
    		
    		int result = prefixSum[x2][y2] - prefixSum[x2][y1-1] - prefixSum[x1-1][y2] + prefixSum[x1-1][y1-1]; 
    		System.out.println(result);
    	}
    }
}