[Silver 3] 11659번 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

이 문제는 DP를 통해 해결할 수 있다.

DP를 통해 누적합을 계산한다.

i와 j사이의 누적합은 DP[j] - DP[i-1] 값이 된다.

즉, 1 2 3 4 5 6 7 8 9 에서 3과 8 사이의 값은

(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) - (1 + 2) = (3 + 4 + 5 + 6 + 7 + 8) 이된다.

 

#include <iostream>

using namespace std;

int N, M;
int arr[100001];
int dp[100001];
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	dp[1] = arr[1];
	dp[2] = arr[2] + dp[1];
	for (int i = 3; i <= N; i++)
		dp[i] = arr[i] + dp[i-1];

	for (int k = 0; k < M; k++) {
		int i, j;
		cin >> i >> j;
		cout << dp[j] - dp[i - 1] << '\n';
	}
}