백준 11659. 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

문제

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

 

해답

구간 합 문제는 처음 풀어봤는데, DP와 비슷하게 푸는 것이라 생각했다.

숫자를 받고 각 구간의 합을 저장하는 배열을 만든 뒤, 끝 구간까지 합 - 시작 구간 직전까지의 합을 구하면 된다.

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

ls = [0] + list(map(int, input().split()))
dp = [0] * (n+1)
for i in range(1, n+1):
	dp[i] = dp[i-1] + ls[i]
for _ in range(m):
	s, e = map(int, input().split())
	print(dp[e] - dp[s-1])