배열과 리스트: 구간합 구하기 (백준 11659)

 

11659번: 구간 합 구하기 4

 

 

난이도: 실버 3

풀이: 먼저 입력받은 값을 배열로 저장하고, 합배열을 생성한다. 그리고 합배열을 사용하여, 더 빠르게 연산을 수행할 수 있다.

 

 

 

import java.util.*;
import java.io.*;
 
public class P11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N        = Integer.parseInt(st.nextToken());
        int M        = Integer.parseInt(st.nextToken());
        
        st            = new StringTokenizer(br.readLine());
        int A[]    = new int[N+1];
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int S[]     = new int[N+1];
        S[1]        = A[1];
        for (int i = 2; i <= N; i++) {
            S[i] = S[i-1] + A[i];
        }
        
        int sum;
        for (int i = 1; i <= M; i ++) {
            st    = new StringTokenizer(br.readLine());
            int H        = Integer.parseInt(st.nextToken());
            int W     = Integer.parseInt(st.nextToken());
            sum        = S[W] - S[H-1];
            
            System.out.println(sum);
        }
        
    }
}