[BOJ-11659][구간합] 구간 합 구하기4 -Java

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

11659번: 구간 합 구하기 4

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 boj_11659_구간합구하기4 {
	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 N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int nums[]=new int[N];
		int sum[]=new int[N+1];
		
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nums[i]=Integer.parseInt(st.nextToken());
		}
		
		
		sum[0]=0;
		for(int i=0; i<N; i++) { //구간합 구하기
			sum[i+1]=sum[i]+nums[i];
		}
		
		for(int k=0; k<M; k++) {
			st = new StringTokenizer(br.readLine());
			int i=Integer.parseInt(st.nextToken())-1;
			int j=Integer.parseInt(st.nextToken())-1;
			bw.write(sum[j+1]-sum[i]+"\n");
		}
		bw.flush();
	}

}

소요시간 : 14분

 

구간 합을 구하는 문제입니다. 

문제 조건이 아래와 같기 때문에 구간합을 찾기 위해 O(N*M)으로는 풀 수가 없습니다.

 

자 그럼 구간합을 어떻게 구하냐?  백준의 문제 예제로 한번 구해보자

 

5 4 3 2 1 이라는 배열(nums)이 있다.

 

sum [0]은 0으로 잡고 sum [i+1]=sum [i]+nums [i]의 식을 통해서 누적합을 더해준다. 

 

nums [] ->  5 4 3 2 1

sum []  ->   0 5 9 12 14 15

 

처럼 결과가 나올 것이다.

 

여기서 sum[i]의 값은 0~nums [i-1]까지의 합이다.

그렇다면 구간합은 어떻게 구할까?? 문제처럼 2~4의 구간합을 구해보자.

(문제 상에서는 1~3이지만 배열은 0부터 시작하니 1~3의 구간합을 구해보자)

 

1~3까지의 합 = 4 + 3 + 2 = 9이다.

저말은 0~3까지의 구간합에서 0~0까지의 구간합을 빼주면 된다는 소리다.

식으로 변환해보면 sum [4] - sum [1] = 14 - 5 = 9처럼 나온다.

 

이를 이용해 누적합을 구하는 시간복잡도는 O(N)

누적합을 통해 구간합을 구하는 시간복잡도는 O(1)에 구할 수 있다.

 

끝~