[백준] 1309번 동물원

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

1309번: 동물원

동적계획법 문제이다. 동적계획법 문제는 점화식만 잘 세우면 된다.

나는 일단 4까지는 노가다로 구한 뒤 규칙을 찾았다.

점화식은

dp[i] = 2 * dp[i - 1] + dp[i - 2]

0	1	2	3	4	5	6	7	8	9	10
1	3	7	17	41	99	239	577	1393	3363	8119

#include <iostream>
#include <vector>
using namespace std;

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