https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
풀이 1
Brute-Force로 풀어봤으나 시간초과
N, M = map(int, input().split())
nums = list(map(int, input().split()))
totals = []
for _ in range(M):
total = 0
i, j = map(int, input().split())
for k in range(i-1, j):
total += nums[k]
totals.append(total)
for s in totals:
print(s)
풀이 2
DP의 memoization 느낌으로 1~N번째까지의 합을 미리 저장해놓고 사용하는 식으로 풀이.
따로 구간합(prefix sum) 이라고 알고리즘 이름이 있는 듯..?
N, M = map(int, input().split())
nums = list(map(int, input().split()))
dp = [nums[0]]
for i in range(1, N):
dp.append(dp[i-1]+nums[i])
results = []
for _ in range(M):
i, j = map(int, input().split())
if i == 1:
results.append(dp[j-1])
else:
results.append(dp[j-1] - dp[i-2])
for r in results:
print(r)