백준_11659번_구간 합 구하기 4_자바

백준_11659번_구간 합 구하기 4_자바 풀어보도록 하겠습니다.

 

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

11659번: 구간 합 구하기 4

 

해당 문제는 문제 자체에 어려움은 없으나,

 

제한 부분을 보시면 아래와 같이 범위가 넓어서 2중 for문으로 풀이시 시간 초과가 나타나는 함정이 있습니다.

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

시간 초과만 유의하여 최초에 값을 받을때 배열에 이전 칸들의 합을 저장하는 합배열을 만들어 주시면 쉽게 풀이가 가능합니다.

 

풀이 소스는 아래를 참고 바랍니다.

 

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

public class Main {

    static int[] arr;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(arr[b]-arr[a-1]+"\n");
        }

        System.out.println(sb);
    }

}