[백준/python] 1912 연속합

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

1912번: 연속합

구간합 알고리즘

크기가 N인 배열에 부분합을 구하는 연산을 M번 수행해야 한다고 하자.

li[l] + li[l+1] + li[l+2] + ・・・ + li[r]는 다음과 같은 코드를 통해 구할 수 있다.

ans = 0
for i in range(l,r):
	ans += li[i]

l, r의 범위가 최악의 경우 0 ~ N-1이므로, 연산의 시간 복잡도는 O(N)이다. 이 연산을 M번 수행해야 하므로 최종적인 시간복잡도는 O(NM)을 갖는다.

이 복잡도를 줄이기 위해 누적합 알고리즘을 사용한다. 누적합 알고리즘의 기본 구조는 sum(li[:r])-sum(li[:l-1]) 이다. 구간합을 구하기 위해 뺄셈 연산 1번만 수행하면 되므로 O(1)의 복잡도를 갖는다. 이 연산을 M번 수행해야 하므로 O(M)의 복잡도를 갖는다. 누적합을 저장할 배열은 O(N)으로 최종적인 복잡도는 O(N+M)이다.

누적합 알고리즘을 통해 효율적으로 구간합 구하는 방법

1. 일단 누적합을 저장할 배열을 만들고, 피보나치 형태로 각각의 위치에 합을 구해준다.

p_sum = [0]*(n+1)
for i in range(1,n+1):
    p_sum[i] = p_sum[i-1]+li[i-1]

*누적합을 구할 때에는 헷갈리지 않기 위해 인덱스를 1부터 사용한다.

2. 구간합 구하기

for _ in range(m):
    l,r=map(int, input().split())
    print(p_sum[r]-p_sum[l-1])

---

전체코드

from sys import stdin
input = stdin.readline
n = int(input())
li = list(map(int, input().split()))
m = int(input())

p_sum = [0]*(n+1)
for i in range(1,n+1):
    p_sum[i] = p_sum[i-1]+li[i-1]

for _ in range(m):
    l,r=map(int, input().split())
    print(p_sum[r]-p_sum[l-1])