[python 파이썬] 백준 11659번 구간합구하기 4

 

11659번: 구간 합 구하기 4

풀이1 - 시간초과 

 

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

nlist = list(map(int,sys.stdin.readline().split()))

for _ in range(m):
  i,j = map(int,input().split())
  sum=0
  for i in range(i-1,j):
    sum+=nlist[i]
  print(sum) 
#시간초과 

 

 

풀이2 - 정답

단순 sum으로 구하면 시간초과가 나와 왤까 고민중 찾아봤는데 이런 문제일경우 '누적합'이라는 개념을 사용해서 풀어야한다고 알게되었다. 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums_add = [0]
for i in range(n):
    nums_add.append(nums_add[-1]+nums[i])
for _ in range(m):
    i, j = map(int, input().split())
    if i == 1:
        print(nums_add[j])
    else:
        print(nums_add[j]-nums_add[i-1])

 

 

참고

https://alpyrithm.tistory.com/87