3. 구간 합 구하기1

문제: 백준 온라인 저지 11659번

 

수 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

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer input = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(input.nextToken());
        int m = Integer.parseInt(input.nextToken());
        
        //합 배열
        int[] arr = new int[n + 1];
        arr[0] = 0;        
        input = new StringTokenizer(bf.readLine());
        for(int i = 1; i <= n; i++){
            arr[i] = arr[i - 1] + Integer.parseInt(input.nextToken());
        }
        
        //구간 합
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int k = 0; k < m; k++){
            input = new StringTokenizer(bf.readLine());
            int i = Integer.parseInt(input.nextToken());
            int j = Integer.parseInt(input.nextToken());
            bw.write(Integer.toString(arr[j] - arr[i-1]));
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
    }
}

 

추가 설명

: 구간 합 알고리즘을 사용하면 시간복잡도를 감소시킬 수 있다. 또한 Scanner를 사용하면 시간 초과가 발생할 우려가 있기 때문에 Buffer를 사용한다.