백준] 2003 - 수들의 합2

시간 제한 : 0.5초

메모리 제한 : 128MB

입력

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int n, m, s, e, sum = 0, cnt = 0;
	cin >> n >> m;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	s = 0, e = 0;
	while (1)
	{
		if (sum >= m)
			sum -= arr[e++];
		else if (s == n)
			break;
		else
			sum += arr[s++];
		if (sum == m)
			cnt++;
	}

	cout << cnt;
}

Tip

투 포인터 알고리즘이라고 표현이 되어 있다. 슬라이딩 윈도우를 생각하고 문제를 풀면 되는 문제이다.