그리디를 졸업했냐 ...? 라고 한다면 아직 보류라고 하겠다.
흥미를 찾기 위해 하는 새로운 알고리즘 누적합!

1. 내 풀이: 실패

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = list(map(int, input().split()))

for _ in range(m):
    i, j = map(int, input().split())
    total = sum(nlist[(i-1):j])
    print(total)
    

풀이가 너무 쉬워서 당연히 시간 초과 뜨겠구나 했더니 ... 역시나였다.
더 고민해보는 것도 의미가 있겠으나 나는 바로 답을 봤다.

2. 다른 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = list(map(int, input().split()))
prefix_total = [0]

temp = 0
for i in nlist:
    temp += i
    prefix_total.append(temp)

for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_total[j] - prefix_total[i-1])
    

풀이 출처: https://ywtechit.tistory.com/79

위의 풀이처럼 풀게 되면 시간 복잡도가 언제나 O(M+N)으로 고정이 되기 때문에 유용하다.
그래서 누적합이라고 불리는 것 같다.

3. 마치며

어떤 식으로 풀어가야하는지도 알았으니 하나 더 풀어볼까!