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

문제

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

풀이

Two Pointer

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태의 알고리즘
• 이중 for문을 이용해서 모든 경우의 수를 구할 수도 있지만, 투포인터 알고리즘을 이용하면 시간을 O(N)으로 단축시킬 수 있음

ex) 연속된 수들의 합, 부분 배열의 합

1. 두 포인터가 같은 방향으로 진행하는 방법
   전부 양수여야 함
   연속하는 부분합이 특정값과 일치하는지
   
   
2. 두 포인터가 다른 방향으로 진행하는 방법
   정렬해야 함
   두 원소의 합이 특정값과 일치하는지 (연속하지 않아도 됨)

sol)
1. start와 end포인터 0으로 초기화
2. 합이 M보다 작으면 end포인터를 이동시켜 값을 크게 해주기
3. 합이 M보다 크면 start포인터를 이동시켜 값을 작게 해주기
4. 합이 M과 같으면 count++, start포인터 이동시키기

코드

#include <iostream>

using namespace std;

int n, m;
int a[10001];

int main() {
	int cnt = 0, start = 0, end = 0, sum = 0;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	/* 투포인터 알고리즘 */
	while (end <= n) {
		if (sum < m) {
			sum += a[end];
			end++;
		}
		else {
			if (sum == m)	cnt++;
			sum -= a[start];
			start++;
		}
	}

	cout << cnt << endl;

	return 0;
}