[#알고리즘/DP/[백준]11659번: 구간 합 구하기 4(python)]

Question

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

Code

import sys

input = sys.stdin.readline

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

for _ in range(m) :
    answer = 0
    i, j = map(int, input().split())
    for a in range(i-1, j) :
        answer += number[a]
    print(answer)

처음엔 위와 같이 인덱스로 접근하여 합을 구하면 시간초과가 발생한다. 따라서 dp를 이용하여 문제를 다시 해결하였다.

import sys

input = sys.stdin.readline

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

# 인덱스의 누적합을 담을 dp 배열 (ex) dp[2] = number[1] + number[2])
dp = [0] * (n + 1)
dp[1] = number[0]

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

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