[Python] 백준 - 구간 합 구하기 4

문제

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

11659번: 구간 합 구하기 4

 

---

풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = list(map(int, input().split()))
prefix_sum = [0]
temp = 0

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

for i in range(m):
    s,e = map(int, input().split())
    print(prefix_sum[e] - prefix_sum[s-1])

 

---

설명

- 구간 합 알고리즘 사용! 위에서 import sys 를 해주지 않으니 시간 초과 오류 발생했었음

* 합 배열 공식

S[i] = S[i-1] + A[i]

 

*구간 합 공식

S[j] - S[i-1]

 

 

ex. A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

S[1] = A[0] + A[1]

S[5] - S[1] = A[2] + A[3] + A[4] + A[5]