코테 백준 11659 실버3

백준 11659

이문제를 봤을때 엄청 쉬워보여서 정말 문제 그대로 i부터 j까지 for문을 이용해서 풀었는데 시간초과라고 떴다.
데이터의 크기를 고려를 안해 시간복잡도를 O(N^2)으로 했기때문이다.

import sys
input=sys.stdin.readline

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

그래서 고등학교때 수열의 합이 생각이났다. 만약 수열들의 합들이 나열될때

ex)
수열들의 합이 또 하나의 수열(3번째 수열의 값은 1-3번째까지의 수열의 합)들이 있을때 3번째부터 6번째까지의 합은 결국 (1-6번째 수열의 합) - (1-2번째 수열의 합)을 계산해주면 된다.

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
num=list(map(int,input().split()))
dp=[0]*(n+1)

for i in range(1,n+1):
    dp[i]+=dp[i-1]+num[i-1]

for i in range(m):
    i,j=map(int,input().split())
    print(dp[j]-dp[i-1])