문제
https://www.acmicpc.net/problem/11659
풀이
누적합 알고리즘을 사용하는 문제
처음 문제를 접했을 때 호기롭게 슬라이싱 후 sum()을 이용해 문제를 해결했읍니다..
시간초과가 발생해 문제가 있음을 알았고 누적합 알고리즘을 이용하여 효율적으로 코드를 작성하니 문제가 해결되었습니다.
누적합 배열 생성
num = [0] # 누적합 배열
for i in range(n):
num.append(arr[i] + num[i]) # num의 i번째 값과 arr의 i번째 값을 더하여 줍니다.원하는 구간의 합을 출력하기 위해서는 j(i<j)번째 값에서 i-1번째 값을 빼주시면 됩니다.
ex)[5,4,3,2,1] 배열이 있을 때 누적합 배열은 [0,5,9,12,14,15]가 됩니다.
1~3 구간의 합을 구할 때 우리는 5+4+3을 구해야 하고 이를 누적합 배열에서는 3번 인덱스인 12에서 0번 인덱스인 0을 빼주어야 올바른 값이 나오게 됩니다.
코드
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
arr = list(map(int,input().split()))
num = [0]
for i in range(n):
num.append(arr[i] + num[i])
for _ in range(m):
i,j = map(int,input().split())
print(num[j]-num[i-1])