[백준, 자바, 15649번] 구간 합 구하기 4

풀이

• 해당 문제는 누적 값 문제이어도 
• 단순히 주어진 범위의 값을 더하면 되는 거 아님? 하고 접근했는데 
• 시간초과나서 확인해보니까 최악이면 100억번 연산을 해야해서 
• 마사카... 어쩌지 하고 생각해보니
• 그냥 배열의 값을 저장할 때 이전값에 더한 값을 넣고
• 아래와 같이 e 인덱스에 해당하는 배열 값에 s-1 인덱스 값을 빼주면 
• 단순히 해결할 수 있는 문제였음.
• 또한 출력이 많아질 수 도 있기에 bw로 write와 flush로 출력

 

import java.io.*;
import java.util.*;

public class _11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) arr[i] = arr[i-1]+Integer.parseInt(st.nextToken());

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            bw.write(arr[e]-arr[s-1]+"\n");
        }
        bw.flush();
    }
}