[백준] 11659 구간 합 구하기 4

백준 11659번 구간 합 구하기 4

투 포인터 / 누적 합

 

 

 

 

[문제]

 

 

 

리스트가 주어졌고 구간의 합을 구하는 문제임을 파악하자.

 

구간의 합 알고리즘을 넣지 않으면 시간초과가 나는 문제이다.

 

기본적으로 M개의 쿼리가 수행할 때마다 전체 리스트의 구간 합을 모두 계산하는 경우는 O(NM)의 시간복잡도를 가진다.

하지만 N개의 리스트의 각 구간에 대해서 합산값을 미리 구해놓으면 O(N+M)의 시간복잡도를 가진다.

즉, 접두사 합을 이용해 시간초과를 해결할 수 있다.

 

 

 

[과정]

 

1. 리스트의 각 구간에 대해서 접두사 합을 계산하여 배열(prefix_sum)에 저장
2. 쿼리를 수행

 

 

 

[소스코드]

 

# 구간 합 구하기 4

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
data = list(map(int, input().split()))
query = []

for i in range(m):
    x,y = map(int, input().split())
    query.append([x,y])
    
sum_value = 0
prefix_sum = [0]

for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

for x,y in query:
    print(prefix_sum[y]-prefix_sum[x-1])

 

 

 

---

 

 

[통과]