[백준/11659/파이썬] 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

Problem

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

조건 

• 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
• 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

SOL

 

python의 slicing 기능을 이용해도 상관없지만, 누적합을 이용해서 풀어보았다.

 

누적합 배열이 있을 때, a~b까지의 합을 구하려면, arr[b] - arr[a-1]을 해주면 된다.(아주 간단한 개념이다)

import sys
input= sys.stdin.readline
N,M=map(int,input().split())
arr=[0]+list(map(int,input().split()))

for i in range(1,N+1):
    arr[i]=arr[i]+arr[i-1]
#print(arr)
#
for i in range(M):
    a,b=map(int,input().split())
    print(arr[b]-arr[a-1])