백준 11659 c++ "구간 합 구하기 4" -PlusUltraCode-

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

 

[필자 사고]

구간 합을 구해야 되는 문제이다.

문제에서 주어진대로 1~3의 숫자들의 합을 하나씩 구하다 보면 시간초과가 나오게 된다.

 

그 이유는 O(n^2)의 성능으로 N=10^5이기 때문이다.

 

필자는 이러한 이유로 아래와 같은 배열을 만들었따.

 

S[i] = S[i-1] + a[i]    (i>=1)

 

이 배열의 뜻은 i번째 배열은 1,2,3,4,5,....i 의 값들의 합으로 이루어진 배열이다.

 

즉 1~3의 합을 구하기 위해서는

S[3] - S[0]을 하게 되면 된다.

[소스 코드]

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> arr;
vector<int> S;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1,0);
	S.resize(N + 1,0);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void makeSum() {

	for (int i = 1; i <= N; i++) {
		S[i] = S[i-1] + arr[i];
	}
}

void Solution() {
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		cout << S[end] - S[start - 1] << '\n';
	}
}

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

	Input();
	makeSum();
	Solution();

}