[백준] 11659. 구간 합 구하기 4 - 파이썬

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

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