[백준 2003] 수들의 합 2 (C++)

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

2003번: 수들의 합 2

문제

---

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

투포인터 문제.

start와 end를 0으로 두고, end까지의 합을 구한다.

만약 end까지의 합이 M이라면 정답을 1증가시키고, 더 크다면 start를 증가시키고 start부터 end까지의 합을 다시 구한다. (start를 증가시키기 전에 start index에 위치한 값만큼 빼주면 새로운 start부터 end까지의 합이 된다.)

해당 과정이 완료되면 end를 증가시킨다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N;
	long long M;
	cin >> N>>M;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int start = 0;
	int end = 0;
	long long sum = 0;
	long long answer = 0;
	while (end < N)
	{
		sum += arr[end];
		while (sum >= M && start <= end )
		{
			if (sum == M)
			{
				answer++;
			}
			sum -= arr[start];
			start++;
		}
		end++;
	}
	cout << answer << "\n";
	return 0;
}