[C++] 백준 2749 피보나치 2

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
	long long iNumber = 0;
	std::cin >> iNumber;
 
	int iFirst = 0;
	int iSecond = 1;
	int iCount = 0;
 
	std::vector<int> vec = {};
	vec.push_back(0);
	vec.push_back(1);
 
	while (true)
	{
		if (!iFirst && iSecond == 1 && iCount)
			break;
 
		int iTemp = iFirst;
		iFirst = iSecond;
		iSecond = (iTemp + iFirst) % 1000000;
 
		vec.push_back(iSecond);
 
		++iCount;
	}
 
	std::cout << vec[iNumber% iCount];
 
	return 0;
}

처음엔 공간복잡도는 생각안하고 풀었습니다.

이전에 푼 피사노주기를 이용해서 풀었습니다.

벡터 이용해서 바로 접근할 수 있도록 만들었는데 공간복잡도가 너무 커서 다시 제작

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
	long long iNumber = 0;
	std::cin >> iNumber;
 
	int iFirst = 0;
	int iSecond = 1;
	int iCount = 0;
 
	while (true)
	{
		if (!iFirst && iSecond == 1 && iCount)
			break;
 
		int iTemp = iFirst;
		iFirst = iSecond;
		iSecond = (iTemp + iFirst) % 1000000;
 
		++iCount;
	}
 
	int N = iNumber % iCount;
 
	iFirst = 0;
	iSecond = 1;
 
	if (!N)
	{
		std::cout << 0;
		return 0;
	}
 
	else if (N == 1)
	{
		std::cout << 1;
		return 0;
	}
 
	for (int i = 1; i < N; ++i)
	{
		int iTemp = iFirst;
		iFirst = iSecond;
		iSecond = (iTemp + iFirst) % 1000000;
	}
 
	std::cout << iSecond;
 
	return 0;
}

벡터 사용하지 않고 풀었더니 공간복잡도가 현저히 낮아졌습니다.

최대 150만번이라 시간복잡도도 차이가 안났습니다.