[백준/누적합] 11659: 구간 합 구하기 - 파이썬

문제

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

11659번: 구간 합 구하기 4

 

제출한 풀이

import sys
input = sys.stdin.readline

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

sum_list = [0] * (n+1)
sum_list[1] = num_list[0]

for i in range(2, n+1):
    sum_list[i] = sum_list[i-1] + num_list[i-1]

for i in range(m):
    a, b = map(int, input().split())
    print(sum_list[b] - sum_list[a - 1])

 

누적합 알고리즘을 사용하여 푸는 문제

리스트 슬라이스를 이용해서 sum 연산을 하게 되면 시간복잡도가 O(N^2)이 되기 때문에 시간초과 발생한다.

누적합 알고리즘을 통해 시간복잡도를 O(N)까지 줄여서 풀어야 한다.

 

누적합 알고리즘의 원리는 여기에 정리해 두었다.