[백준11659] / 구간 합 구하기 4 - 누적합

 

백준11659

 

 

푼 날짜 : 2024.09.21

푼 문제 : [11659] / 구간 합 구하기 4

사용한 언어 : python

알고리즘 : 누적합

 

 

푼 방법 :

구간이 정해질 때마다 합을 계산하는 것이 아닌 미리 누적된 합을 구해서 구간에 맞는 값을 출력하도록 했다.

따라서 미리 반복문으로 합을 계산했고 start와 end값을 받아 sum_배열의 인덱스 end의 값에서 start-1의 값을 빼줬다.

 

 

코드: 

import sys

N, M = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))

sum_ = [0 for _ in range(N+1)]
sum_[1] = lst[1]
for i in range(1, N+1):
    sum_[i] = sum_[i-1] + lst[i-1]

for _ in range(M):
    start, end = map(int, sys.stdin.readline().split())
    print(sum_[end]-sum_[start-1])

 

 

옛날에 그냥 sum(lst[start, end+1])했다가 시간초과 났던 문제 ^___^

효율적으로 코드를 짜자 !