[백준] 구간 합 구하기4(11659)

수가 주어졌을 때 i번째 수부터 j번째 수까지 합을 구하는 문제이다.

입력으로 N과 M이 10만까지 주어지기 때문에 O(n^2)으로는 문제를 해결할 수 없다.

매번 더하는 방식으로는 문제를 해결하지 못한다.

 

그럼 어떻게 해결을 해야 하는 것인가?

미리 더해놓음으로써 매번 더하는 작업을 없앨 수 있다. (arr[i]+=arr[i-1])

 

입력을 받는 동시에 미리 더한다.

5 9 12 14 15

이렇게 더한 후 만약 2 3 이 입력으로 들어오면 2 이전에 값은 필요가 없어지니 12-5=7을 출력하면 된다.

i부터 j까지의 합을 얻으려면 i 이전에 값을 제거해 주는 작업이 꼭 필요하다. (arr[j]-arr[i-1])

 

그리고 출력하는 작업이 많다 보니 출력으로 인한 시간초과를 피하기 위해 

ios::sync_with_stdio(false);
cin.tie(NULL);

이 부분을 추가해줘야 한다.

그리고 줄 바꿈은 endl대신 '\n'을 사용해 준다.

#include <iostream>

using namespace std;

int arr[100001];

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

	int N = 0;
	int M = 0;

	cin >> N>>M;

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

	for (int i = 0; i < M; i++)
	{
		int num1 = 0;
		int num2 = 0;
		cin >> num1 >> num2;
		cout << arr[num2] - arr[num1 - 1]<<'\n';
	}



	return 0;
}