백준1309 - 동물원

https://www.acmicpc.net/problem/1309

1309번: 동물원

풀이가 되게 짧아서 허탈한 문제였다. 점화식이 간단하니 스스로 세워서 풀어보도록 하자

#include <iostream>
using namespace std;

int mat[100001];

int main() {
	int n;
	cin >> n;

	/*
		3
		7
		17 = 7 * 2 + 3
		41 = 17 * 2 + 7
		.
		.
		.
		따라서 점화식은 : a(n) = 2 X a(n - 1) + a(n - 2), a(1) = 3, a(2) = 7, (n >= 3)
	*/
	mat[1] = 3;
	mat[2] = 7;
	for (int i = 3; i <= n; i++) {
		mat[i] = (2 * mat[i - 1] + mat[i - 2]) % 9901;
	}
	cout << mat[n];
}