동물원 C++ - 백준 1309

https://www.acmicpc.net/problem/1309

이 문제는 백준 쉬운 계단 수에서 배운

dp 테이블을 활용해 풀었다.

먼저 i번째 칸 왼쪽에 사자를 배치하는 경우의 수는

1. i-1번째에서 하나도 배치하지 않음
2. i-1번째에서 왼쪽에 배치함

이 있고 오른쪽은 왼쪽과 비슷하게

1. i-1번째에서 하나도 배치하지 않음
2. i-1번째에서 오른쪽에 배치함

이 있다. 그리고 하나도 배치하는 않는 경우의 수는

1. i-1번째에서 하나도 배치하지 않음
2. i-1번째에서 왼쪽에 배치함
3. i-1번째에서 오른쪽에 배치함

이렇게 i와 i-1번째의 dp테이블 관계를 정리하고 점화식을 세웠다.

코드는 다음과 같다.

#include <iostream>
#define MAX 100000
#define MOD 9901
typedef long long ll;
using namespace std;

ll dp[MAX][3]; // 0 lay left 1 lay right 2 not lay
ll ans=0;
int n;

int main(){
	cin >> n;
	dp[0][0]=1;
	dp[0][1]=1;
	dp[0][2]=1;
	for(int i=1;i<n;i++){
		dp[i][0]=(dp[i-1][1]+dp[i-1][2])%MOD;
		dp[i][1]=(dp[i-1][0]+dp[i-1][2])%MOD;
		dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
	}
	for(int i=0;i<3;i++){
		ans+=dp[n-1][i];
	}
	cout << ans;
}