[C++] 백준 11659. 구간 합 구하기 4

🌽 문제

🥕 입출력

🥔 풀이

싸피 때 배웠던 슬라이딩 도어 뭐 그런 알고리즘이 어렴풋이 생각났다.

구간을 입력받을 때마다 누적합을 계산하는 게 아니라,
v[i]: arr[i]까지의 누적합으로 두어 미리 구한 뒤
a ~ b까지 누적합: v[b] - v[a - 1]로 바로 계산하여 출력하는 방식이다.

이 때 누적합은 현재의 배열값에 이전까지의 누적합을 더해서 계산한다.

🥬 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, a, b;
	cin >> n >> m;
	
	vector<int> arr(n + 1);
	vector<int> v(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	v = arr;
	
	for (int i = 2; i <= n; i++)
		v[i] += v[i - 1];
	
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		int sum = v[b] - v[a - 1];
		cout << sum << "\n";
	}
	
	return 0;
}

🥜 채점

ios::sync_with_stdio(0); cin.tie(0); 이거 필수!