백준 11659 - Java

import java.util.Scanner;

public class BJ11659 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //n입력
        int m = sc.nextInt(); //m 입력
        int[] n_arr = new int[n+1]; //n arr 생성
        n_arr[0] = 0;
        //arr 입력받기
//        for(int i=1;i<=n;i++){
//            n_arr[i] = sc.nextInt();
//        }
        //누적 합으로 배열 다시 생성.
        for(int i = 0; i < n; i++){
            n_arr[i+1] = n_arr[i] + sc.nextInt();
        }
        //연산
        for(int i=0;i<m;i++){
//            int count =0;
            int start = sc.nextInt();
            int end = sc.nextInt();
            System.out.println(n_arr[end]-n_arr[start-1]);
//            for(int j=start;j<=end;j++){
//                count += n_arr[j];
//            }
//            System.out.println(count);
        }
    }
}

 

시간복잡도 생각안하고 O(n^2)으로 풀었더니 time limit에 걸리게 되었다. 그래서 사전 연산을 해야한다는 것을 알게 되었고  사전 연산후 문제를 풀었다.