백준] 1904 - 01타일

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫 번째 줄에 자연수 N이 주어진다.(N≤1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

소스코드

#include <iostream>
using namespace std;
long long dp[1000001] = { 1, 1, };
int main()
{
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
	}
	cout << dp[n];
}

Tip

피보나치 수열