백준 JAVA 11659 구간 합 구하기4

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

11659번: 구간 합 구하기 4

접근방법

 - 구간합을 구하는 문제. 

 - 이중for문을 사용하면 시간초과가 날거라고 생각했다.

   ( M 이 100,000 까지인데, 100,000 * 100,000 하면 1초가 훌쩍넘어버린다 )

- 따라서 구간합을 먼저 구해 저장할 수 있도록 sun 배열을 생성했다.

- 입력범위가 1~3 / 2~4 / 5~5 이기때문에 sum의 0의 인덱스는 사용하지 않으려고 sum 배열의 길이를 n+1 로 설정했다.

-  a = 2  / b = 4일때, sum[4] - sum[a-1] 를 이용하면 사이의 합을 구할 수 있다.

 

package BAEKJOON.Silver.Ⅲ;
/**
 * 시간 제한   메모리 제한 제출 정답 맞힌 사람  정답 비율
 * 1 초 256 MB 43853  19420  15114  42.873%
 */

import java.util.Scanner;

public class NO11659 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        int[] sum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        sum[1] = arr[0];
        for (int i = 1; i < n; i++) {
            sum[i + 1] = sum[i] + arr[i];
        }

        // System.out.println(Arrays.toString(sum));
        // [5, 9, 12, 14, 15]

        for (int i = 0; i < m; i++) {
            int answer = 0;
            int a = sc.nextInt();
            int b = sc.nextInt();

            answer = sum[b] - sum[a - 1];

            System.out.println(answer);
        }
    }
}