백준 2018 수들의 합.

풀이 전략

: n은 1000만 이고, 부분 연속합이고,
15의 경우, 아래의 4가지 경우가 있음.

• 즉, 15까지 진행을 한다는 것이기 때문에 15 하나 연속값 추출
  1000만 * 1000만 이고, 시간 제한은 2초여서 ,2억 초과함.

• -> 연속적인 원소들 가운데서 부분합을 구하는 투포인터를 사용하자.
  O(N + ?) 의 비용으로 처리 가능함.

코드

#include <iostream>
using namespace std;
#include <string>

#include <vector>
#include <limits.h>
#include <algorithm>
#include <map>
#include <future>
#include <thread>
#include <numeric>
#include <stack>
#include <queue>
#include <memory>
#include <set>
#include <string>
#include <stack>
#include <mutex>
#include <ostream>



int main()
{
	int n;
	cin >> n;
	// n은 1000 만임.

	// 1 2 3 4 5 6 7 8 9 10

	// 1000 만 * 1000만 비용을 가지고 옴. 
	// 15는 15 1개로 만족함.
	// 제한시간은 2초 , 즉 2억이니까. 

	// 문제 풀이는 연속된 원소들끼리의 부분합을 구하는 것임. 
	// 그리고 오름차순으로 되어있기 때문에 1번 풀이로 접근하자.
	// 투포인터로 접근하자. 
	// while문으로 n번까지 진행함.

	int startP = 1;
	int endP = 2;
	int cnt = 0;
	int temp = startP + endP;

	// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	while (n != startP)
	{
		if (temp < n)
		{
			++endP;
			temp += endP;
		}
		else if (temp > n)
		{
			temp -= startP;
			++startP;
			//temp += startP;
		}
		else if (temp == n)
		{
			++cnt;
			++endP;
			temp += endP;
		}

	}

	cout << cnt + 1;

}