baekjooon(11659_구간 합 구하기 4)_python_[누적합]

1) 문제

2) 예시

3) 제출

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
li = list(map(int, input().split()))
sumLi = [0]
for i in range(0, len(li)):
    sumLi.append(li[i] + sumLi[i])
answer = ""

for k in range(0, m):
    i, j = map(int, input().split())
    answer += str(sumLi[j] - sumLi[i - 1]) + "\n"
print(answer.rstrip())

4) 메모리/시간/코드 길이

5) PLUS

처음에 해결했지만 시간초과 난 방법 = > 슬라이싱 이용

BUT:

N의 최대 : 10만, M의 최대 : 10만으로

한 케이스당 답을 구할 때 첫 번째 반복문 만 10만 번이 돌아가게 된다.

10만 케이스를 입력 받을 경우엔 10만 * 10만이 된다.

 

그러므로 :

리스트에 처음부터 그 리스트까지 누적 합을 구해주면 시간을 줄일 수 있다!

 

예를 들어:

M이 10만이고, 5만 개의 케이스의 구간이 전부 다 5만 부터 8만이라면,

sumLi[5만]에는 li[ : 5만]의 합이 들어가 있고,

sumLi[8만]에는 li[ : 8만]의 합이 들어가 있어,

li[5만] ~ li[8만]을 그때마다 다 더해서 출력하는 것을 5만 번 반복하는 것이 아니라,

sumLi[8만] - sumLi[5만]을 5만 번 출력해 주면 된다!

 

li 리스트의 5만 번째 원소부터  li리스트의 8만 번째 원소 까지의 값을 전부 더해서 8만 - 5만의 시간 복잡도가 생기는 대신,

sumLi[8만] - sumLi[5만]의 연산 한 번만 하면 되니 훨씬 시간이 줄게 된다.