[백준 11659번] 구간 합 구하기 4 - python

문제 링크 

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

11659번: 구간 합 구하기 4

풀이

- sum 사용해서 푸니깐 시간 초과  

#시간 초과
n, m = map(int,input().split())

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

for _ in range(m):
  a, b = map(int,input().split())

  print(sum(num[a-1:b]))

- 앞서 백준 ATM 이라는 문제를 풀이했을 때 dp로 풀면 시간이 훨씬 줄어드는 것을 알 수 있었다. 

- 그래서 누적 합을 구해놓고 구간 차이를 계산하여 풀어주니 통과 

import sys
input= sys.stdin.readline

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

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

dp = [0] * (n+1)

dp[1] = num[0]

# 누적 합저장 
for i in range(2,n+1):
  dp[i] += dp[i-1] + num[i-1]

for _ in range(m):
  a, b = map(int,input().split())
  
  # 구간 합 구하기
  print(dp[b]-dp[a-1])