[백준] 11659번 구간 합 구하기 4 - 구간합 알고리즘

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner kb = new Scanner(System.in);
    	int N = kb.nextInt();
    	int M = kb.nextInt();
    	int[] numbers = new int[N+1];
    	int[] sumNumbers = new int[N+1];
    	StringBuilder sb = new StringBuilder();
    	
    	for(int i=1; i<N+1; i++) {
    		numbers[i] = kb.nextInt();
    		sumNumbers[i] = sumNumbers[i-1]+ numbers[i];
    	}
    	
    	for(int x=0; x<M;x++) {
    		int i = kb.nextInt();
    		int j = kb.nextInt();
    		int sum = sumNumbers[j] - sumNumbers[i-1];
    		sb.append(sum).append('\n');
    	}
    	
    	System.out.println(sb.toString());
    	
    	
    }
}

 

 

아무 생각없이 풀었다가 시간초과 난 문제 

구간 합을 미리 구하면 시간 복잡도가 O(N)으로 감소한다.