백준 구간 합 구하기 4 11659

 

import sys
input = sys.stdin.readline
n,m = map(int ,input().split())
check = list(map(int, input().split()))
prefix_sum = [0]*(n+1)
answer = 0
for i in range(1,n+1):
    prefix_sum[i] = prefix_sum[i-1] + check[i-1]
for _ in range(m):
    a,b = map(int, input().split())
    answer = prefix_sum[b] - prefix_sum[a-1]
    print(answer)

처음 문제를 풀때는 구간별로 전부 수를 더하였지만, 시관초과가 나왔다.O(n^2)의 시간복잡도가 필요하기 때문에 시간초과가 나온것 같다.

그래서 누접합이라는 알고리즘을 사용했더니, 시간초과 오류를 해결할수 있었다. 누적합의 시간복잡도는 O(n)이다.

누적합(Prefix_sum) 알고리즘은 배열의 각 요소에 대해 그 이전까지의 모든 요소를 더한 값을 미리 계산해 저장하는 알고리즘이다.

위의 문제를 적용하게 되면,a구간부터 b구간 까지의 합을 구해야하는 문제이다.

이문제에서 b까지 더한 구간에서 a까지 더한 구간을 빼주게 된다면, a~b이 나오게 된다.