문제
https://www.acmicpc.net/problem/11441
접근
- 주어진 수의 개수 n과 구간의 수 m의 범위가 1 <= n <= 100000, 1 <= m <= 100000 이므로, 매 구간마다 합을 구하면 시간초과
- 누적합을 이용하면 시간복잡도 O(n + m)에 해결 가능
풀이
- s[i] = a[1] 부터 a[i] 까지의 합을 미리 구해놓은 뒤, 주어진 구간 [start, end]에 대해 s[end] - s[start - 1]을 계산한다.
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = a[i] + s[i - 1]
m = int(input())
for _ in range(m):
start, end = map(int, input().split())
print(s[end] - s[start - 1])
'Python > Coding Test' 카테고리의 다른 글
1781 컵라면 (0) | 2022.02.10 |
---|---|
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |
13702 이상한 술집 (0) | 2022.02.08 |
2110 공유기 설치 (0) | 2022.02.08 |