[코딩테스트 연습(Python)] 백준 11659번_구간 합 구하기 4(누적합/DP)

 

1. 문제 검토

제시된 N과 M이 각각 100,000까지 될 수 있으므로 시간 복잡도상 일반적인 풀이는 일반적인 sum으로는 불가능할 것으로 보였다.

역시나 아래 sum을 활용한 풀이는 시간초과

import sys

input = sys.stdin.readline

n,m = map(int,input().split())


ij = list(map(int, input().split()))

print(ij)

for i in range(m):
    a, b = map(int,input().split())
    print(sum(ij[a-1:b]))

2. 누적합을 이용한 풀이

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = [0]
arr += list(map(int, input().split()))

for i in range(1, n+1):
    arr[i] = arr[i] + arr[i-1]

for _ in range(m):
    i, j = map(int,input().split())
    print(arr[j]- arr[i-1])

3. DP를 이용한 풀이

DP를 이용한 풀이도 결국 미리 계산한 누적합을 답안 도출에 사용하는 것이기 때문에 DP를 위한 배열을 선언해주는 것 말고는 다를것이 없다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = list(map(int, input().split()))

dp = [0] * (n+1)

for i in range(1, n+1):
    dp[i] = dp[i-1] + arr[i-1]

for _ in range(m):
    i, j = map(int,input().split())
    print(dp[j]- dp[i-1])