[Python] 백준 11659번 : 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

---

 문제 풀이

가장 기본적인 누적 합 문제이다!

누적 합은 DP의 개념과 비슷하다고 볼 수 있다.

리스트를 추가로 구현하고 계산된 값을 미리 넣어둔다.

 

n~m까지의 구간 합은 m까지의 누적 합과 n까지의 누적 합을 뺀 것이다!

 느낀 점

시간 초과가 뜨길레 뭐지..? 했는데 단순히 모르는 알고리즘이었다.

그렇다고 엄청 특별한 알고리즘은 아니어서 금방 해결할 수 있었다!

 코드

from sys import stdin

N, M = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
prefix_sum = [0]

tmp = 0
for i in arr:
    tmp += i
    prefix_sum.append(tmp)
    
for n in range(M):
    i, j = map(int, stdin.readline().split())
    print(prefix_sum[j] - prefix_sum[i-1])