[BOJ / C++] 2003 : 수들의 합2

링크

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

2003번: 수들의 합 2

 

풀이 과정

투포인터로 풀면 O(n)시간 안에 풀리는 문제이다.

다만 유의해야할점은

4 4

1 5 2 2

와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다.

따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다. 

 

코드

#include <iostream>
using namespace std;

int main()
{
	long n,m;

	int l=0;
	int arr[100000];

	cin >> n;
	cin >> m;

	int r = 0;
	for (int i = 0; i < n; i++)cin >> arr[i];

	int cnt = 0;
	int sum = arr[0];
	while (r >= l && r < n) {
		if (sum== m) {
			cnt++;
			sum += arr[++r];
		}
		else if (sum > m) {
			sum -= arr[l++];
			if (l > r) {
				r = l;
				sum = arr[r];
			}

		}
		else {
			sum += arr[++r];
		}

	}
	cout << cnt;
}