[Python] 11659. 구간 합 구하기 4

import sys


input = sys.stdin.readline

n, m = map(int, input().split()) # 수의 개수 n, 합을 구해야 하는 횟수 m
numbers = list(map(int, input().split())) # n개의 수

# dp 리스트 만들기
dp = [0 for _ in range(n+1)]
for i in range(n):
    dp[i+1] = dp[i] + numbers[i]
    
for _ in range(m):
    i, j = map(int, input().split())

    print(dp[j] - dp[i-1])

 

풀이 

1. 먼저 dp[i+1]에 numbers[i]까지(numbers[:i+1])의 합을 저장하여 dp리스트를 만든다. 
2. i와 j가 주어졌을 때, i는 구간의 시작 j는 구간의 끝이니 dp[j] - dp[i-1] 을 하면 해당 구간의 합을 구할 수 있다.

Python과 그냥 PyPy를 써도 시간초과가 나서 import sys를 해야 겨우 시간초과의 늪에서 빠져나올 수 있는 문제였다.