백준 11659 - 구간 합 구하기 4

백준 11659 - 구간 합 구하기 4

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

풀이

시간 제한이 1초이고, 수의 개수 N 의 범위는 1 ~ 100,000 이다.

최악의 경우 i가 0, j 가 N 일때, 시간 복잡도가 O(N) 이므로,

시간 제한에 걸리게 된다.

즉, 수 N 개가 주어졌을 때, i 번째 수부터 j 번째 수까지의 합을 구하는

전형적인 구간 합 (Prefix sum) 문제이다.

문제에서 구간 합만을 요구하므로, 구간 합 배열 sumArr 을 선언하여

N 개의 수가 입력될때마다 구간 합을 넣어주고, 인덱스를 입력받아 답을 출력한다.

코드