004. 구간 합 구하기5(백준11660)

문제

문제 분석하기

배열의 크기 : $1<= N <= 1024$
질의 개수 : $1 <= M <= 100,000$

질의가 들어올때 마다 로직을 수행해 합을 구하기보다는
정답판 같이 바로 답을 출력할 수 있는 형태를 만들어 놓는게 좋다.

구간합을 이용해 접근해보자

손으로 풀어보기

예제의 값을 사용해 구간합배열을 만들어 주었다.

구간합배열의 (x, y) 는 기존 배열의 (0, 0) 부터 (x, y) 까지의 합이다.

오른쪽 배열을 만들기위한 코드는 어떻게 접근해야 할까?

기존배열의 (0, 0) ~ (0, 1)의 구간 합 + (0, 1) ~ (1, 0)의 구간 합 + (1, 1)의 값 - 중복된 (0, 0)의 값

위와같이 계산하면 구간합배열의 (1, 1)의 값인 8 이 나오게 된다.

코드로 일반화 해보자

A = 기존배열
S = 구간합배열

S[ i ][ j ] = S[ i-1 ][ j ] + S[ i ][ j-1 ] - S[ i-1 ][ j-1 ] + A[ i ][ j ]

슈도코드 작성하기

N(배열 크기 입력받기) M(질의 수 입력받기)

A(원본배열 선언)
for(N까지) {
	A배열 초기화 (요소 입력받기)
}

S(구간합 배열 선언)
for(N까지) {
	원본배열을 이용해 구간합배열 초기화
}

입력받은 구간의 합 출력하기

코드 구현하기

import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
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 arrCnt = Integer.parseInt( st.nextToken( ) );  
		int queryCnt = Integer.parseInt( st.nextToken( ) );  
  
       // 입력받은 값을 이용해 원본 배열 선언 및 초기화  
		int[][] originArr = new int[ arrCnt + 1 ][ arrCnt + 1 ];  
		for ( int i = 1; i <= arrCnt; i++ ) {  
			st = new StringTokenizer( br.readLine( ) );  
			for ( int j = 1; j <= arrCnt; j++ ) {  
				originArr[ i ][ j ] = Integer.parseInt( st.nextToken( ) );  
			}       
		}  
       // 원본배열을 이용해 합배열 선언 및 초기화  
       // S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + Origin[i][j]  
		int[][] sumArr = new int[ arrCnt + 1 ][ arrCnt + 1 ];  
		for ( int i = 1; i <= arrCnt; i++ ) {  
			for ( int j = 1; j <= arrCnt; j++ ) {  
				sumArr[ i ][ j ] =  
				sumArr[ i ][ j - 1 ] + sumArr[ i - 1 ][ j ] - sumArr[ i - 1 ][ j - 1 ] + originArr[ i ][ j ];  
			}       
		}  
       // 입력받은 구간의 합 구하기  
		for ( int i = 0; i < queryCnt; 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( ) );  
			
			bw.write(sumArr[ x2 ][ y2 ] - sumArr[ x1 - 1 ][ y2 ] - sumArr[ x2 ][ y1 - 1 ] + sumArr[ x1 - 1 ][ y1 - 1 ] + "\n" );  
		}  
       bw.flush( );  
       bw.close( );  
    }
}