[BOJ/C++] 2018 수들의 합-5

투 포인터를 이용하여 문제를 해결할 수 있습니다

시간 제한이 2초이고 N의 최댓값은 10,000,000 이므로 $O(nlogn)$인 알고리즘을 사용하면 시간초과가 발생하므로 $O(n)$인 알고리즘을 사용해야 합니다.

3가지의 경우의 수로 투 포인터를 이동할 수 있습니다.

1. sum > N -> start_index++; sum-=start_index;
2. sum < N -> end_index++; sum+=end_index;
3. sum == N -> end_index++; sum+=end_index; count++;

// boj s5 2018
// 수들의 합 5

#include <iostream>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	int start_idx=1, end_idx=1;
	int sum = 1, count = 1;

	cin >> N;

	while (end_idx != N)
	{
		if (sum == N)
		{
			count++;
			end_idx++;
			sum += end_idx;
		}
		else if (sum < N)
		{
			end_idx++;
			sum += end_idx;
		}
		else
		{
			sum-=start_idx;
			start_idx++;
		}
	}

	cout << count;

	return 0;
}