1309번: 동물원

Code

• python

제출 날짜

2021/05/30

메모리

3192 KB

시간

0 ms

#include <iostream>

int N;
int dp[100002];
std::pair<int, int> inp[100002];

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N;
}

void solve()
{
	inp[1].first = 1;
	inp[1].second = 1;
	dp[1] = 1;
	for (int i = 2 ; i < N + 1 ; i++)
	{
		inp[i].first = (inp[i - 1].second + dp[i - 1]) % 9901;
		inp[i].second = (inp[i - 1].first + dp[i - 1]) % 9901;
		dp[i] = (inp[i - 1].first + inp[i - 1].second + dp[i - 1]) % 9901;
	}
	std::cout << (inp[N].first + inp[N].second + dp[N]) % 9901;
}

int main()
{
	input();
	solve();
	return (0);
}