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