[🥈3 / 백준 11659 / 파이썬] 구간 합 구하기 4

 

11659번: 구간 합 구하기 4

 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력  5 3 5 4 3 2 1 1 3 2 4 5 5

예제 출력  12 9 1

 

풀이

 

누적 합(prefix sum) 알고리즘을 통해 구간 합을 빠르게 구해 출력하는 문제이다.

 

배열에서 구간의 합을 구할 때 배열과 구간의 크기가 모두 크다면,

배열의 구간에서 원소를 일일이 훑으며 더해주는 것은 시간 복잡도가 O(N²)에 가깝게 되므로 성능이 매우 좋지 않다.

 

따라서 입력 받은 배열을 누적 합 배열로 바꾸고,

구하려 하는 구간 i, j에 해당하는 두 원소의 차를 구해 그 구간의 합을 구하는 방식을 사용한다.

 

예제에서 나온 [5, 4, 3, 2, 1] 의 누적 합 배열을 구하면 다음과 같다.

 

pfs = [0, 5, 9, 12, 14, 15]

 

앞에 0은 계산시 인덱스를 초과하지 않게 하기 위해 붙인다.

이제 구간 i, j의 합을 구하고자 한다면 pfs[j] - pfs[i-1] 을 해주면 간단히 구할 수 있다.

 

위에서 만약 구간 1~5의 합을 구하고자 한다면,

pfs[5] - pfs[1-1] = 15 - 0 = 15로 두 번의 연산으로 구할 수 있게 된다.

 

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

pfs = list(map(int,input().split()))
for i in range(n-1):
    pfs[i+1] += pfs[i]
pfs = [0] + pfs

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