[백준 알고리즘] 백준 11659번 구간 합구하기 자바(Java)

1)문제번호:11659번

 

2)문제 출처

www.acmicpc.net/problem/11659  

11659번: 구간 합 구하기 4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

 

출력

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

 

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 

5 3
5 4 3 2 1
1 3
2 4
5 5

 

예제 출력 

12
9
1

 

풀이

- 구간 합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용한 특수한 목적의 알고리즘이다. 

 

구간 합의 핵심 이론

구간 합 알고리즘을 활용할려면 먼저 합 배열을 구해야 한다. 배열 A가 있을대 합 배열 S는 아래와 같다.

합 배열 S 정의
S[i] = A[0] + A[i] + A[2] .... + A[i-1] + A[i]

합배열 S를 만드는 공식

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

구간 합을 구하는 공식
S[j] - S[i-1]

public class BackJun11659 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        int suNo = Integer.parseInt(stringTokenizer.nextToken()); // 숫자개수
        int quizNo = Integer.parseInt(stringTokenizer.nextToken()); // 질의개수
        long[] S = new long[suNo + 1];
        stringTokenizer = new StringTokenizer(br.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(br.readLine());
            int i = Integer.parseInt(stringTokenizer.nextToken()); //질의 범위 받기
            int j = Integer.parseInt(stringTokenizer.nextToken()); //질의 범위 받기
            System.out.println(S[j] - S[i - 1]);  //구간 합 출력하기
        }
    }
}