Algorithm/BOJ

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

징늬2 2021. 2. 15. 23:29
반응형

 

 

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

풀이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

반응형