백준 11659번 - 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

처음에는 이렇게 풀었다. 그냥 흔히 떠올릴만한 풀이이다.

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long n, m;
	cin >> n >> m;
	long input;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> input;
		v[i] = input;
	}

	for (int i = 0; i < m; i++)
	{
		long sum = 0;
		long a, b;
		cin >> a >> b;
		for (int k = a - 1; k <= b - 1; k++)
		{
			sum += v[k];
		}
		cout << sum << '\n';
	}
	return 0;
}

놀랍게도 어찌보면 당연히 시간초과가 뜬다.

m이 엄청 크면 어떻게할건데...

 

그렇기에 생각한 것이 아예 누적합, 즉 arr[2]면 1부터 2까지의 합

arr[5]면 1부터 5까지의 합을 저장해놓은 배열을 만들어놓고

시작과 끝 인덱스를 받으면 이에 맞는 합을 출력하게 해주었다.

#include <bits/stdc++.h>
using namespace std;

long long dp[100000];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	int start, end;
	long long num;
	cin >> n >> m;

	dp[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> num;
		dp[i] = dp[i-1] + num;
	}

	for (int i = 0; i < m; i++)
	{
		cin >> start >> end;
		cout << dp[end] - dp[start - 1] << '\n';
	}
	
	return 0;
}