백준 1309(동물원)

www.acmicpc.net/problem/1309

1309번: 동물원

500문제 달성 위해서 랜덤문제를 푸는 첫 문제. 

 

그냥 점화식 찾는 문제이다. 점화식을 잘 찾아보자 

근데 생각보다 점화식이 너무 어려웠다. 

 

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

 

#include<iostream>
using namespace std;
#define MAX 100005

int dp[MAX];

int solve(int idx) {
	if (dp[idx]) return dp[idx];

	int ret=0;
	ret = (solve(idx-1)*2 + solve(idx-2)) % 9901;
	return dp[idx] = ret;
}

int main() {
	dp[0] = 1;
	dp[1] = 3;
	int N;
	cin >> N;
	cout << solve(N) << '\n';
}