[11659] 구간 합 구하기 4

혹시나 했지만 역시나 시간 초과 풀이

import sys

input = sys.stdin.readline

n,m = map(int, input().split())

nlist = list(map(int, input().split()))

for _ in range(m):

    first, second = map(int, input().split())

    sum = 0

    for i in range(first-1, second):

        sum += nlist[i]

    print(sum)

 

시간을 줄일 수 있는 방법이 뭐가 있을까 고민했는데

그냥 절반으로 줄여서 실행해봤다.

이 때 양옆의 값에서부터 가운데로 왔다. 홀수면 가운데 값만 하나 추가해봤다.

이것도 시간초과가 났다 ㅜ

import sys

input = sys.stdin.readline

n,m = map(int, input().split())

nlist = list(map(int, input().split()))

for _ in range(m):

    first, second = map(int, input().split())

    k = second - first + 1

    first -= 1

    second -= 1

    sum = 0

    if k%2 == 0:

        for i in range(k//2+1):

            sum += nlist[first+i] + nlist[second-i]

    else:

        for i in range(k//2):

            sum += nlist[first+i] + nlist[second-i]

        sum += nlist[(first+second)//2]

    print(sum)

 

결국 제미나이의 도움을 받아 누적합 문제라는 것을 알았다.

비슷한 문제 중에 꿀따기라는 문제를 풀었던 것 같았는데..

 

import sys

input = sys.stdin.readline

n,m = map(int, input().split())

sumList = [0]

sum = 0

nlist = list(map(int, input().split()))

for i in nlist:

    sum += i

    sumList.append(sum)

   

for _ in range(m):

    first, second = map(int, input().split())

    print(sumList[second] - sumList[first-1])