[파이썬] 백준 22659 : 구간 합 구하기4

[파이썬] 백준 22659 : 구간 합 구하기4

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

11659번: 구간 합 구하기 4

실버 3

누적 합

---

입력받는 리스트의 범위가 100000이나 되므로 반복문으로 단순구현하면 시간초과가 난다.

따라서 각 인덱스까지의 값을 따로 저장할 리스트를 구현하고 필요한 값을 뽑아쓰는 방식으로 접근해야 한다.

반복문을 사용해 이를 만들어 낼 수 있지만,

itertools의 accumulate를 사용하면 해당 리스트의 누적합을 쉽게 구할 수 있다.

[5, 4, 3, 2, 1]를 넣으면 [5, 9, 12, 14, 15]라는 값으로 반환한다.

 

 

import sys; input = sys.stdin.readline
from itertools import accumulate
N, M = map(int, input().split())
lst = list(map(int, input().split()))
nlst = list(accumulate(lst))
ans = []
for _ in range(M):
    i, j = map(int, input().split())
    if i <= 1:
        print(nlst[j-1])
    else:
        print(nlst[j-1] - nlst[i-2])