[백준/Python]11659_구간 합 구하기 4

문제

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

11659번: 구간 합 구하기 4

풀이

처음에 m 만큼 리스트를 슬라이싱해서 풀었을 때 시간초과가 났습니다.

i번째 항까지 누적 합을 나타낸 리스트를 미리 만들고, 합하는 연산을 줄여서 통과했습니다.

코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
memoization = [0] * n  # 누적 합의 값을 미리 구해놓는다
for i in range(n):
    if i == 0:
        memoization[i] = numbers[i]
        continue
    if i != 0:
        memoization[i] = memoization[i - 1] + numbers[i]
for _ in range(m):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    result = memoization[end - 1] - memoization[start - 1] + numbers[start - 1]
    print(result)