구간 합 빠르게 계산하기

 

답안 예시

# 데이터의 개수 N과 데이터 입력받기
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix_Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산(세 번째 수부터 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])

 

작성한 답안

# 데이터의 개수 N과 데이터 입력받기
n = 5
m = [10, 20, 30, 40, 50]

# 접두사 합 배열 계산
p = [0] * (n+1)
sumNum = 0
for i in range(n):
    sumNum += m[i]
    p[i+1] = sumNum

# 구간 합 계산(세 번째 수부터 번째 수까지)
left = 3
right = 4
print(p[right] - p[left-1])

70

 

출처 : https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9&t=1009s