백준 1309 동물원

코드:

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
#define MAX 100001
int n, d[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	d[0] = 1;
	d[1] = 3;
	if (n == 1)
	{
		cout << d[1];
		return (0);
	}
	for (int i = 2; i <= n; i++)
		d[i] = (2 * d[i - 1] + d[i - 2]) % 9901;
	cout << d[n];
}