[백준 - 1309] 동물원

#include <iostream>
#define MOD 9901
using namespace std;

unsigned long long int dp[100'001][2];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	dp[1][0] = 1;
	dp[1][1] = 1;

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

	cout << ((dp[N][1] * 2) + dp[N][0]) % MOD;
	return 0;
}

---

||사고 과정

일단 경우의 수를 i가 3일때 까지 그려보았다.

DP로 해결하려 했으니 dp[i - 1]에 추가를 하려고 했던것같다.

 

그러던 중 추가될 수 있는 마지막이 O X, X O, X X 이렇게 3가지인걸 확인 후

테이블을 2차원 배열로 하려고 생각을 했었다.

 

이렇게 생각하고 나니까 각 추가될 수 있는 개수가 규칙적으로 나오길래 예외 테스트를 하고 작성하여 풀이했다.

 

dp[i - 1]에 어떠한 걸 덧 붙일 때 크게 나오는 경우의 수를 찾아서 풀이 하는게 종종 보여서

이런 방법을 잘 기억해두고 있어야겠다.

---

||사용 기법

• DP