투포인터란?

2개의 포인터를 조작하면서 원하는 결과값을 얻는 알고리즘입니다.

기본적인 사용법은 위 사진과 같습니다.
StartIndex인 A와 EndIndex인 B사이를 순회하면서, 주어진 조건을 만족하는지 체크.
이후, 조건에 따라서, StartIndex를 +1하거나 EndIndex를 +1하여 탐색 범위를 늘려갑니다.

여기서 만약 동일한 범위(상단의 그림에서는 5로 표현되었습니다)를 유지한다면 슬라이딩 윈도우 기법이 됩니다.

이러한 투포인터는 배열이나 리스트와 같은 자료구조에서 흔히 사용되는 알고리즘 기법입니다.

예제문제

수들의 합5

백준 문제 링크

자연수 N을, 몇 개의 연속된 자연수의 합으로 나타내는 것이 가능합니다.
예를들어, 주어진 N이 15라면,
15 = 15
15 = 7+8
15 = 4+5+6
15 = 1+2+3+4+5
다음과 같이 네 가지 경우의 수가 있을 것입니다.

이렇게 주어진 N값을 연속된 부분 수열로 표현할 수 있는 가짓수를 구하는 방법에는 여러가지가 있겠지만,
투포인터를 이용하여 구현해보도록 하겠습니다.

투포인터의 핵심은 반복문을 체크할, Start와 End 인덱스를 조건에 맞게 적절히 이동하는 것입니다.

만약 N이 15일 때,
부분수열의 합이 15를 초과한다면.
Start를 ++하여, 수열의 합을 줄입니다. (부분 수열이 작아짐)

1+2+3+4+5+6 = 21로써, N인 15를 초과합니다.
따라서, satrt를 ++하여. index를 1로 옮깁니다.
이렇게 되면, 2+3+4+5+6 = 20이 되어 수가 줄어듭니다.

반대로 부분수열의 합이 15 미만일 경우,
end를 ++하여, 수열의 합을 늘립니다.(부분 수열이 커짐)

부분수열 6+7 = 13으로 N인 15에 미치지 못합니다.
따라서, end를 ++하여 index를 7로 옮깁니다.
이렇게 되면, 6+7+8 = 21이되어 수가 커집니다.

이러한 방식으로 satrt인덱스가 end 인덱스 보다 같거나 커질 때까지 순회를 반복하는 것이 투포인터를 이용한 구현법입니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N;
	cin >> N;
	int start = 1;
	int end = 1;
	int sum = 0;
	int cnt = 0;

	while (start <= N)
	{
		if (sum < N)
		{
			sum += end;
			end++;
		}
		else if (sum == N)
		{
			cnt++;
			sum -= start;
			start++;
		}
		else
		{
			sum -= start;
			start++;
		}
	}

	cout << cnt;
}