[Python] 11659번 구간 합 구하기 4

11659번: 구간 합 구하기 4 (acmicpc.net)

11659번: 구간 합 구하기 4

---

 

22/09/08

 

 

누적 합 알고리즘을 사용하여 해결할 수 있는 전형적인 문제로, 만약 이 문제를 해결하고 싶다면 누적 합 알고리즘에 관해서 조금 알아두는 것이 편할 것이다.

---

 

문제 접근 방식:

 

 

그냥 누적 합 알고리즘을 그대로 구현한 것이다.

 

누적 합 알고리즘은 위와 같은 상황처럼 부분 합을 구하는데 그 쿼리의 양이 감당할 수 없을 정도로 많을 때, 이를 쉽게 구하고자 고안된 알고리즘으로, 메모이제이션 기법을 활용하여 구한다.

 

예를 들어, 내가 인덱스 5부터 8까지의 합을 구한다고 치면, 미리 1부터 8까지 구해놓은 누적합 리스트 원소와 1부터 4까지 구해놓은 누적합 리스트 원소를 빼주면 되는 형식이다.

 

이렇게 미리 구해놓으면 미리 구해놓는 시간이 따로 걸릴 순 있어도 각각의 쿼리를 처리하는 속도가 혁신적으로 빨라지기 때문에 가능하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11659번 구간 합 구하기 4
# 누적 합
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
num_li = list(map(int, input().rstrip().split()))
accum_sum = [0, num_li[0]]
for i in range(1, N):
    accum_sum.append(accum_sum[i]+num_li[i])
for _ in range(M):
    i, j = map(int, input().rstrip().split())
    print(accum_sum[j] - accum_sum[i-1])