[백준11659번] 구간 합 구하기 4 / Python3

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

예제 입력 1

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1

12
9
1

나의 풀이

문제의 제한사항으로 N이 100,000까지로 for문을 중첩하는 O(n^2)이상의 알고리즘으로는 해당 문제를 통과할 수 없다.

문제를 접근하는 방법은 i부터 j까지의 합 = j까지의 합에서 i-1까지의 합을 뺀 값 이다. 따라서 초기 입력받은 배열을 한 번 순회하면서 해당하는 인덱스까지의 합을 저장해두고(dp[i] = dp[i-1] + arr[i-1]) M개의 입력에 따라 dp[j] - dp[i-1]을 출력해주면 된다.

코드

# 11659번 구간 합 구하기 4
from sys import stdin

n, m = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().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, stdin.readline().split())
    print(dp[j] - dp[i-1])