[C/C++ 백준 1309번] 동물원 (Silver 1)

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

1309번: 동물원

2 * i에 대해 가능한 경우의 수 dp[i]라고 했을 때, 사자를 한 마리 넣어보면 dp만으로 계산할 수 없다는 것을 알 수 있다. 한칸만 튀어나온 꼴의 경우의 수도 따로 계산해서 dp2[i]로 만들어 주자.

 

즉,

이런 꼴의 모양이 dp[10]이고,

									X

이런식으로 한칸 비운것이 dp2[10]이다. 이 둘에 대해 점화식을 쓰는 건 그리 어렵지 않아 쉽게 풀 수 있다.

 

#include <cstdio>
int main(void){
	int N, dp1[100001]={0,3,7,17,},dp2[100001]={0,2,5,};
	scanf("%d",&N);
	for(int i=3; i<=N; i++){
		dp1[i]=2*dp2[i-1]+dp1[i-1];
		dp2[i]=dp2[i-1]+dp1[i-1];
		dp1[i] %= 9901;
		dp2[i] %= 9901;
	}
	printf("%d",dp1[N]);
}