백준 - 1484번 : 다이어트 (C++)

풀이 방법 : 수학(?), 브루트포스

수학으로 풀었다고 하기도 민망하다 태그를 보니까 투 포인터로도 가능하다는데 범위 보니까 싹 다 검사해도 시간초과에 안걸릴 것 같아 그냥 무식하게
G = Cur^2 - Prev^2
Cur^2 = G + Prev^2
를 만족시키는 자연수들을 구해주었다.
계속 증가시켜나가다가 반복자가 되는 녀석의 i^2 - (i-1)^2가 만약 G보다 크다면 루프를 종료해주었다.

입력으로 들어오는 G의 최대가 100,000라고 했으므로 최악의 경우에도 약 5만번쯤 연산하면 끝난다. 이 정도면 2초는 낭낭(?)하게 통과할 것이므로 그냥 이렇게 무식하게 풀어주었다.

#include <iostream>
#include <set>
#include <cmath>

using namespace std;

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

	unsigned int G;
	cin >> G;

	set<unsigned int> setNum;
	unsigned int i = 1;

	while(true)
	{
		if ((i * i) - ((i - 1) * (i - 1)) > G)
			break;

		unsigned int TempNum = G + i * i;
		unsigned int Cur = sqrt(TempNum);

		if (Cur * Cur == TempNum)
			setNum.insert(Cur);
		
		++i;
	}

	if (setNum.empty())
	{
		cout << -1;
		return 0;
	}

	auto iter = setNum.begin();
	auto iterEnd = setNum.end();

	for (; iter != iterEnd; ++iter)
	{
		cout << *iter << '\n';
	}
}