[알고리즘] C++ 백준 11659 구간 합 구하기 4

 

백준 11659

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

11659번: 구간 합 구하기 4

풀이 전 나의 생각

주어진 N의 범위를 보면 100000개 까지 주어질 수 있다.

이 조건의 의미는 2차원 배열과 2중 for문은 사용이 불가능하다는 것이다.

 

그럼 1차원 배열로 for문 하나만 써서 해결하면 쉽게 풀릴 수 있는 문제라고 힌트를 준 것이다.

문제의 풀이를 생각해보면 구간의 합을 구해야 한다. 그러면 각 상황마다의 구간 합을 모두 구해주고

이를 이용하면 될 것이다.

 

그럼 구간의 합을 다 구했다고 가정하고 예제의 <5 ,4, 3, 2, 1>에서 시작 값 2와 마지막 값 4를 예시로 들어보겠다.

두번 째 까지의 구간 합 (5 + 4 = 9) 과 네번 째 까지의 구간 합 (5 + 4 + 3 + 2 = 14)이 있다.

두번 째 부터 네번 째까지의 구간 합을 구하려면 4 + 3 + 2를 해야 한다.

그럼 구간의 합 4는 5 + 4 + 3 + 2, 여기서 5만 빼주면 2부터  4의 구간 합이 나올 것이다.

시작 값 2는 5 + 4 이기 때문에 시작 값 2에서 -1을 빼준 1의 구간 합(5)을 4의 구간합에서 빼주면 2부터 4의 구간 합이 나온다.

 

이 설명을 식으로 표현 하면 arr[end] - arr[start - 1]로 표현할 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

int arr[100001];

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

	int n, 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 start, end;
		cin >> start >> end;

		cout << arr[end] - arr[start - 1] << '\n';
	}
}