동물원 (feat. 백준, 1309번)

동물원
https://www.acmicpc.net/problem/1309

1309번: 동물원

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1309
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	int dp[100001];
	dp[0] = 1, dp[1] = 3;
	cin >> N;
	for (register int i = 2; i <= N; ++i)
		dp[i] = (dp[i - 2] + dp[i - 1] * 2) % 9901;
	cout << dp[N] << "\n";
	return 0;
}
// *&)*@*

N=0, 한마리도 없으니 1입니다.

N=1, 한마리도 없는 경우 / 좌측만 있는 경우 / 우측만 있는 경우 총 3입니다.

N=2, 아래와 같은 경우가 있습니다.

X

	X

X

	X

X
	X

	X
X

총 7입니다.

N=3, 아래와 같은 경우가 있습니다.

X

	X

X

	X

X

	X

X
	X

X
X

X
	X

	X
X

	X
X

	X
	X

X
	X

	X
X

X
	X
X

	X
X
	X

총 17입니다.

 

즉 1, 3, 7, 17 로 결과가 도출됩니다.

따라서 dp(N) = dp(N - 1) * 2 + dp(N - 2) 의 점화식이 성립됩니다.