[BOJ] 11659 - 구간 합 구하기 4

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

---

[알고리즘풀이]

A[N] : 처음에 들어온 값들이 저장되어있는 배열.

dp[N] : 1 ~ N 까지의 합이 저장되어있는 배열.

따라서, dp[K] = dp[K-1] + A[K] 가 성립하고 i ~ j 까지의 구간 합은 dp[j] - dp[ i - 1] 이다.

#include <iostream>
#include <cmath>

using namespace std;

int A[100001] = {};
int dp[100001] = {};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	dp[1] = A[1];
	for (int i = 1; i <= N; i++)
		dp[i] = A[i] + dp[i-1];
	
	int x, y;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
			cout << dp[y] - dp[x - 1] << '\n';
	}
	return 0;
}

---