[백준 14246] K보다 큰 구간 (C++)

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

문제

---

 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j] (i≤j)의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오.

입력

---

첫째 줄에는 자연수의 개수 n이 주어진다. (1 ≤ n ≤ 100000)

다음 줄에는 자연수 n개가 주어진다. 자연수는 100,000보다 크지 않다.

그 다음 줄에는 자연수 k가 주어진다. (1 ≤ k ≤ 1,000,000,000)

 

출력

---

특정 구간 [i,j]의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오.

 

문제 풀이

---

투 포인터 문제.

 

주어진 수가 모두 자연수이므로 [i, j]가 k보다 크다면 j보다 큰 모든 수 l에 대해 [i, l]이 k보다 크다. 이를 이용하여 투포인터를 사용하여 i(=투포인터의 start에 해당)를 순차적으로 증가시키며 각 i에 대해 k보다 클 때까지 j(=투 포인터의 end에 해당)를 증가시켜 k보다 첫번째로 큰 구간 [i, j]를 찾는다. 한 i에 대한 j의 탐색을 마치면 투 포인터 end는 k보다 첫번째로 큰 구간 [i, j]에서 j보다 한 칸 뒤를 가리키고 있다. 따라서 이를 원상 복구하기 위해 합에서 이를 제외하고 end도 1 감소시킨다. 이후 다음 i에 대해 탐색하기 위해 합에서 start가 가리키는 값을 빼주고 start를 1 증가시켜주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N, K;
	long long answer = 0;
	cin >> N;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	cin >> K;
	int start = 0;
	int end = -1;
	long long sum = 0;
	while (start < N)
	{
		while (true)
		{
			end++;
			if (end >= N)
			{
				break;
			}
			sum += arr[end];
			if (sum > K)
			{
				answer += N - end;
				break;
			}
		}
		if (end < N)
		{
			sum -= arr[end];
			end--;
		}
		sum -= arr[start];
		start++;
	}
	std::cout << answer << "\n";
	return 0;
}