백준 11659 : 구간 합 구하기 _ 자바 Java

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

11659번: 구간 합 구하기 4

---

* i와 j를 받을 때마다 배열에 저장된 수를 범위에 맞게 더해서 출력하는 방식으로 풀었더니 시간초과가 나와서 

미리 누적합을 배열에 저장해서 i와 j가 주어졌을때 범위 외 누적합을 빼는 것으로 해결함.

예를 들어, 

수의 배열이 5 4 3 2 1 로 입력이 된다면 

배열에는 0 5 9 12 14 15  이렇게 저장이 된다. 

import java.io.*;
import java.util.*;

public class Main {
	static int[] num;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str= br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		int N = Integer.parseInt(st.nextToken());	//수의 개수
		int M = Integer.parseInt(st.nextToken());	//합을 구해야하는 횟수
		num = new int[N+1];	//수의 배열
		
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) {
			num[i]=num[i-1]+Integer.parseInt(st.nextToken());	//누적합 미리 저장 
		}
		
		for(int k=0;k<M;k++) {
			st=new StringTokenizer(br.readLine());
			int i=Integer.parseInt(st.nextToken());	
			int j=Integer.parseInt(st.nextToken());	
			
			System.out.println(num[j]-num[i-1]);
		}

	}//main()
	
}//class Main