백준 1309번: 동물원

[문제 링크]

1309번: 동물원

---

top-down으로 구현하다가 시간초과, 스택오버플로를 겪고 bottom-up으로 구현하였다.

 

이 문제를 N이 3일 때 까지 손으로 풀어보면 간단한 점화식을 발견할 수 있는데 점화식은 다음과 같다.

 

dp(N) = dp(N-1) * 2 + dp(N-2) 

 

점화식은 간단하지만 필자는 위 점화식이 어떻게 참이 되는지 이해를 못하였기 때문에 위 점화식이 아닌 다른 방법으로 풀었다.

 

핵심은 옆에 칸에 사자를 배치했느냐 안했느냐에 따라서 경우의 수가 다르다는 것이다.

---

#include <iostream>
using namespace std;

const int MOD = 9901;
int memo[100001][2];

int Bottomup(int N)
{
	// [i][0] : 이전칸에 배치 했을 경우
	// [i][1] : 이전칸에 배치하지 않았을 경우
	memo[1][0] = 2;
	memo[1][1] = 3;

	for (int i = 2; i <= N; i++)
	{
		memo[i][0] = (memo[i - 1][0] + memo[i - 1][1]) % MOD;
		memo[i][1] = (memo[i - 1][0] * 2 + memo[i - 1][1]) % MOD;
	}

	return memo[N][1];
}

int main(void)
{
	int N;
	cin >> N;

	cout << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 91 day