실버3 구간 합 구하기 4(11659)

11659번: 구간 합 구하기 4

처음에는 아래와 같이 정말 간편하게 풀 수 있을 것이라고 생각하고 풀었다. 아래와 같이 sum과 슬라이싱을 이용했더니 바로 실패했다. 그래서 누적합에 대해서 공부를 했다.

n, m = map(int, input().split())
data = list(map(int, input().split()))
for _ in range(m):
  i, j = map(int, input().split())
  print(sum(data[i-1:j]))

아래는 누적합에 대해서 공부를 좀하고 풀었다. 누적합을 다 저장해놓고 구간을 입력받으면 뒤의 누적합과 앞의 누적합과의 차를 통해서 구간의 누적합을 구할 수 있었다. 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = list(map(int, input().split()))
prefixSum = [0, data[0]]
for i in range(1, n):
  prefixSum.append(prefixSum[i] + data[i])
for _ in range(m):
  i, j = map(int, input().split())
  print(prefixSum[j] - prefixSum[i-1])

가장 어이없었던건 import sys를 통해서 입력을 받지 않으니 바로 시간초과가 난 것이다. 저 2줄을 정말 그냥 넣고 시작해야할 것 같다.