2022.03.07 [백준] (python 파이썬) 구간 합 구하기 4

 

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

11659번: 구간 합 구하기 4

 

---

풀이

이 문제는 주어진 범위를 for문을 돌며 합을 구하면 시간초과가 발생한다. 

그래서 다른 배열에 각 인덱스 까지의 합을 저장한 후, 

i~j까지 합을 sums[i]-sums[j-1]처럼 누적합을 이용하여 구하면 시간초과를 피할 수 있다.

import sys
 
input=sys.stdin.readline
n,m=map(int, input().split())
nums=list(map(int,input().split()))
 
sums=[0]
total=0
for i in range(len(nums)):
    total+=nums[i]
    sums.append(total)
for _ in range(m):
    i,j=map(int,input().split())
    print(sums[j]-sums[i-1])