[백준] 11659번: 구간 합 구하기 4 - java

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

 

문제 분석

 

처음 문제를 보고 단순히 주어진 인덱스에서 for문으로 값을 탐색하여 sum에 더할 수 있으나 빠른 알고리즘을 위해 S[i] = S[i-1] + A[i] 로 배열 값을 저장한 후 합을 출력할때 단순하게 배열값의 차이를 출력하는 방법으로 설계하였다.

 

 

문제 코드

 

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

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

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        int sum = 0;
        int []A = new int[N+1];
        
        stringTokenizer = new StringTokenizer(bf.readLine());
        for(int i=1; i<N+1; i++){
            A[i] = Integer.parseInt(stringTokenizer.nextToken())+ sum;
            sum = A[i];
        }
        for(int j=0; j<M; j++){
            stringTokenizer = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(stringTokenizer.nextToken());
            int y = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(A[y]-A[x-1]);
        }
    }
}