백준 알고리즘

파이썬) 백준 알고리즘 | 11659번 : 구간 합 구하기 4

코딩새내기_ 2022. 3. 2. 12:49

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

 

11659번: 구간 합 구하기 4

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

www.acmicpc.net

백준 11659 '구간 합 구하기 4' 문제입니다.

그냥 구현하면 시간초과가 날 가능성이 크므로 

해당 인덱스까지의 총합을 원소로 가지는 인덱스를 추가로 만들어서 구하면 시간초과를 해결할 수 있습니다.

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
sum_nums = [0]
temp = 0
for i in range(len(nums)) :
    temp += nums[i]
    sum_nums.append(temp)
for i in range(m):
    a, b = map(int, input().split())
    print(sum_nums[b]-sum_nums[a-1])