Koala - 10기/코딩테스트 준비 스터디
[백준/Python] 11659번: 구간 합 구하기 4 (누적합)
쥬발이
2023. 4. 3. 00:51
1. 문제
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
2. 해결방안
당연한 말이지만 .. 누적합을 사용했다
prefix_sum 이라는 배열을 통해 원소를 하나씩 탐색하며 그 원소를 이전까지 더해준 값에 더해서 넣어줬다 ~ !
그리고 i~j 까지의 합은 prefix_sum[j] - prefix_sum[i-1] !!
3. 코드
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
nums = list(map(int,input().split()))
prefix_sum=[0]
sum = 0
for n in nums:
sum += n
prefix_sum.append(sum)
for _ in range(m):
i,j = map(int,input().split())
print(prefix_sum[j] - prefix_sum[i-1])