[Python] 백준 #11659. 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

# 11659 - Python 3

import sys

input = sys.stdin.readline

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

arr = list(map(int, input().split()))
pfs = [0]                                   # pfs list에 미리 0을 추가하여 line 20에서 혼동 방지                       
answer = []                         

summ = 0

for i in arr:
    summ += i
    pfs.append(summ)                        # 누적합(prefix sum)

for _ in range(m):
    x, y = map(int, input().split())

    answer.append(pfs[y] - pfs[x - 1])

for i in answer:
    print(i)

< 누적합 알고리즘 >

- 입력을 받을 때 마다 각 구간의 합을 구하는 것이 아닌, 각 구간까지의 합을 미리 구하고 계산하는 알고리즘

: pfs(prefix sum)을 통하여 원래의 코드보다 시간 단축