(3) 구간 합 구하기

문제

수 N 개가 주어졌을 때 i 번째 수에서 j 번째 수까지의 합을 구하는 프로그램을 작성하시오

 

입력

1번째 줄에 수의 개수 N (1~100,000), 합을 구헤야 하는 횟수 M(1~100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000 보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야 한느 구간 i와 j가 주어진다.

 

출력

총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.

 

예제 입력

5 3		//데이터의 개수, 질의 개수
5 4 3 2 1	//구간 합을 구할 대상 배열
1 3
2 4
5 5

예제 출력

12
9
1

 

먼저, 합의 배열을 만들자.

 

A : 보기 배열

S : 합 배열

 

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

 

구간 i ~ j 를 구하는 구간 합 공식으로 정답을 출력하자.

 

공식 : S[ j ] - S[ i - 1]

 

코드

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

public class P11659_구간합구하기 {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		
		int suNo = Integer.parseInt(stringTokenizer.nextToken());
		int quizNo = Integer.parseInt(stringTokenizer.nextToken());
		
		long[] S = new long[suNo+1];
		
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		
		for(int i = 1; i <= suNo; i++){
			S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
		}
		
		for(int q = 0; q < quizNo; q++) {
			
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());
			
			System.out.println(S[j]-S[i-1]);
			
		}
	}
}

 

---

Reference

백준 온라인 저지 11659번