[🐙 알고리즘] 백준 11659 - 구간 합 구하기4 / Python

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

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

코드

# 11659 구간합 구하기
import sys
input =  sys.stdin.readline

N,M = map(int,input().split())
numbers = list( map(int,input().split()))

#합배열을 구하면 시간복잡도를 크게 줄일 수 있다.
sumNumbers = [0] #이 부분 확인
temp = 0
for i in numbers:
    temp = temp + i
    sumNumbers.append(temp)

# 전체합 배열에서 뒤의수 - 앞의수 +1 한 배열의 값을 반환
for j in range(0,M):
    p,b = map(int,input().split())
    ans = sumNumbers[b] - sumNumbers[p-1]
    print(ans)

풀이

합배열을 미리 구해두고 풀면 시간 복잡도를 크게 줄일 수 있다.
합배열의 공식은 S[i] = S[i-1]+a[i] 이다.

합배열은 sumNumbers로 구해두었고
구간 합 공식은 다음과 같이 이용한다.
S[4] = A[0]+A[1]+A[2]+A[3]+A[4]
S[4] - S[3] = A[4]