C++ 백준 2003번 : 수들의 합 2

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을 넘지 않는 자연수이다.

출력

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

---

풀이

며칠 전에 푼 '수들의 합 5'랑 비슷한 문제였는데 왜캐 어려운지 ,, 생각보다 쉽지 않았다 ... 수들의 합은 end포인터가 끝으로가면 끝낼 수 있었지만, 이 문제는 start포인터도 신경써야한다는 점

반례

4 1

1 1 1 1

3 46

2 23 23

 

두 개의 반례를 보면서 겨우겨우 풀었다 ,,  

end포인터에 마지막에 있을 경우에도 숫자가 일정하게 커지지 않기 때문에 답이 나올 수도 있다! 그래서 start포인터도 옮겨가면서 풀어야 한뎌~~

---

#include <bits/stdc++.h>
using namespace std;
int arr[10001] = { 0, };

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

	int N, M; // 자연수
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int tmp;
		cin >> tmp;
		arr[i] = tmp;
	}
	int start_idx = 0;
	int end_idx = 0;
	int sum = 0;
	int ans = 0;

	while (start_idx <= N) { // start_idx가 마지막에 갈때까지

		if (sum >= M || end_idx==N){  // sum이 더 클 경우 or end가 마지막에 있을 경우
			start_idx++;
			sum -= arr[start_idx];
		}
		else { // 작을경우
			end_idx++;
			sum += arr[end_idx];
		}
		if (sum == M) { // 같을 경우
			ans++;
		}
	}
	cout << ans;

	return 0;
}