백준 11659번 바로가기

첫 번째 시도

# 입력
import sys
read = sys.stdin.readline

n,m = map(int,read().split())
arr = list(map(int,read().split()))

# 처리
for _ in range(m):
  i,j = map(int,read().split())
  print(sum(arr[i-1:j]))

두 번째 시도

# 입력
import sys
read = sys.stdin.readline

n,m = map(int,read().split())
nums = {}
for index, num in enumerate(map(int,read().split())):
  nums[index+1] = num

print(nums)

  
# 처리
for _ in range(m):
  temp = 0
  i,j = map(int,read().split())
  for k in range(i,j+1):
    temp += nums[k]
  print(temp)

세 번째 시도

# 입력
import sys
read = sys.stdin.readline

n,m = map(int,read().split())
arr = [0] + list(map(int,read().split()))
for i in range(1,len(arr)):
  arr[i] = arr[i-1] + arr[i]
  
# 처리
for _ in range(m):
  temp = 0
  i,j = map(int,read().split())
  print(arr[j] - arr[i-1])

CODE REVIEW

  1. 첫 번쨰 시도는 시간초과로 실패했다. list에서 조회하는데 시간이 오래 걸리는듯: 시간복잡도 O(n^2)
  2. 두 번쨰 시도는 list대신 dict를 사용했는데, 여전히 시간초과 발생하더라… pypy3로 돌려도 마찬가지.
  3. 계속 시간초과의 수렁에 빠져서 알고리즘 분류를 참고했다. 누적 합(prefix sum)이라고 나와있는데, $\sum\limits_{i=i}^j = S_{j} - S_{i-1}$ 로 구하는 식이다.