[백준 1904번 C++풀이] - 01타일

걸린 시간: NULL

생각보다 어려웠다.

처음에는 sum함수를 만들어서 그곳에 하나하나 처리한후 저장하는 식으로 했으나, 뭔가 이상하다 생각해서 다른 식으로 생각해보니 그냥 피보나치 함수였다 ㅋㅋㅋ..

또 그냥 입력으로 처리해서 오버 플로우 뜨길래, 나머지만 구해서 저장하는 식으로 처리했다.

DP는 너무 어려운듯..

#include <iostream>
#include <vector>

using namespace std;
int N;
vector <int> s(1000001, 0);
int CW(long long int a)
{
	if (s[a] == 0)
	{
		if (a == 1)
		{
			return 1;
		}
		else if (a == 2)
		{
			return 2;
		}
		else
		{
			s[a - 1] = CW(a - 1) % 15746;
			s[a - 2] = CW(a - 2) % 15746;
			return s[a - 1] + s[a - 2];
		}
	}
	else
	{
		return s[a] % 15746;
	}
	
}
int main()
{

	cin >> N;
	
	cout << CW(N) %15746;
}