[백준 11659 파이썬] 구간 합 구하기 4 (실버 3, 누적합)

알고리즘 유형 : 누적 합
풀이 참고 없이 스스로 풀었나요? : 학습

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))
pre_sum = [0]

temp = 0
for i in arr:
    temp += i
    pre_sum.append(temp)
    
for _ in range(M):
    a, b = map(int, input().split())
    print(pre_sum[b] - pre_sum[a-1])

풀이 요약

1. 이 문제에서 들어온 구간에 대해, 그 때마다 구간 합을 구하면 시간복잡도가 O(NM)이 되므로 너무 오래걸린다.

   이렇게 부분 연속합을 여러 번 구해야할 때, 미리 리스트 arr에 첫 번째 인덱스부터 모든 인덱스까지의 연속합을 구해놓고, 특정 구간 연속합이 필요할 때, 그 구간의 마지막 인덱스에 대한 arr값과 시작 인덱스 - 1의 arr값을 빼서 구해주면 된다.

   arr를 구할 때 시간 복잡도는 O(N), 이 후 M번 연속합을 인덱싱하므로 O(M), 총 O(N+M)이다.

배운 점, 어려웠던 점

• 누적 합을 효율적으로 구하는 테크닉을 배웠다.