[백준 11659] 구간 합 구하기 4 / 자바 / 누적합

문제         

레벨:  S3
알고리즘:  누적합
풀이시간:  16분
힌트 참조 유무: 무

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

1 번째 시도   

문제를 보고 엥 이거 너무 기초적인 문제 아니야? 라고 생각했다가 제한을 보고 생각을 바꿨다. 

100,000(N의 최댓값) x 100,000(M의 최댓값) = 100,000,000,000(1억 초과)이기 때문에 O(n^2) 시간복잡도로는 풀 수 없다.

 

[아이디어]

O(N) 시간복잡도를 생각해봤다. 한번에 탐색으로 1 ~ arr[i]까지 담길 배열을 만드는 것이다. 만약 3~5까지 합을 구하고 싶다면 5인덱스에 있는 값(1~5) - 2인덱스에 있는 값(1 ~ 2)로 구하면 되는 것이다.

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

class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String[] s1 = br.readLine().split(" ");
        
        int N = Integer.parseInt(s1[0]);
        int M = Integer.parseInt(s1[1]);
    
        int[] sum = new int[N+1];
        
        String[] s2 = br.readLine().split(" ");
        sum[0] = 0;
        for(int i = 1; i <= N; i ++) {
            sum[i] = sum[i-1] + Integer.parseInt(s2[i-1]);
        }
        
        for(int i = 0; i < M; i++) {
            String[] s3 = br.readLine().split(" ");
            int start = Integer.parseInt(s3[0]);
            int end = Integer.parseInt(s3[1]);
            System.out.println(sum[end] - sum[start-1]);
        }
    }
}