1309번: 동물원

문제풀이

1. n=1,n=2일때를 대입해서 구해본다.
2. 바로 옆과 위에는 사자가 올 수 없으니, 한줄에 사자를 놓는방법은 3가지이다.

   OX 또는
   XO 또는
   XX 또는
   O : 사자, X : 빈자리

3. n번과 n-1번 사이에 관계식을 구한다.
4. 반복문을 통해 답을 구한다.

DP 풀이

n=1, 답:3 n=2, 답:7 이다.

편의상 OX 케이스를 0, XO를 1, XX를 2로 두자
dp[N][C]=A , N:우리의 크기, C:케이스, A:우리의 크기가 N일때 케이스 C에 대한 경우의 수

예를들어, dp[3][1] = dp[2][0] + dp[2][2] 이다.

점화식

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

실제코드

#define MAX 100000+1
#define Modular 9901

int N;
int dp[MAX][3];
int answer;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	ifstream cin; cin.open("input.txt");


	cin >> N;

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

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

	for (int i = 0; i < 3; i++)
	{
		answer += dp[N][i];
		answer %= Modular;
	}

	cout << answer;
}