[Softeer] 성적 평균

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=389&sw_prbl_sbms_sn=83356

수정 전 코드 : 시간복잡도 O(2N)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

double getAverage(int from, int to, vector<double> v)
{
	double ans = 0;
	double len = to - from + 1;
	for (int i = from; i <= to; i++)
		ans += v[i];
	ans = (round((ans / len) * 100.0))/100;
	return ans;
}

int main()
{
	int N, M;
	cin >> N >> M;

	vector<double> v_score;
	v_score.push_back(0);
	for (int i = 0; i < N; i++)
	{
		double score;
		cin >> score;
		v_score.push_back(score);
	}
	for (int i = 0; i < M; i++)
	{
		int from, to;
		cin >> from >> to;
		printf("%.2f\n", getAverage(from, to, v_score));
	}

	return (0);
}

수정 후 코드 : 시간복잡도 O(1)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;

	vector<int> sum;
	sum.push_back(0);
	for (int i = 1; i <= N; i++)
	{
		double score;
		cin >> score;
		sum.push_back(score + sum[i-1]);
	}
	for (int i = 0; i < M; i++)
	{
		int from, to;
		cin >> from >> to;
		double len = to - from + 1;
		printf("%.2f\n", (sum[to] - sum[from - 1]) / len);
	}

	return (0);
}