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

쉽게 풀 수 있어 보이는 문제지만 우리는 항상 테스트케이스에 대해서 생각을 해야한다.

무지성으로 임시 변수에 계속 값을 더하면

테스트케이스를 전부 감당할 수 없을 정도의 값이 입력되어

시간초과로 틀릴 수 있는 가능성이 크다

이럴 때는 구간 합 알고리즘을 사용하면 된다.

 

구간 합 알고리즘은 간단히 설명하자면

어떤 배열이 주어졌을 때, 다른 임시 배열을 만들어서

그 임시 배열에 원래 배열의 부분 합을 더해주면 된다.

흡사 다이나믹 프로그래밍과 비슷하다고 생각하면 된다.

 

#include <iostream>
using namespace std;
int arr[100001]{ 0, };
int sarr[100001]{ 0, };

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= n; i++) {
		if (i == 0)
			sarr[i] = arr[i];
		else
			sarr[i] = sarr[i - 1] + arr[i];
	}

	int a, b;

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		int sum = 0;
		/*
		for (int k = a - 1; k <= b - 1; k++) {
			sum += arr[k];
		}
		cout << sum << '\n';
		*/
		cout << sarr[b] - sarr[a - 1] << "\n";
	}
}