c언어 1309번 동물원

#include <stdio.h>

int main(void)
{
	int n = 0;
	scanf("%d", &n);
	int a, b, c;
	a=b=c=1;
	for(int i=2; i<=n; i++) {
        int tmp_b, tmp_c;
		tmp_b = (a + c)%9901;
		tmp_c = (a + b)%9901;
		a = (tmp_c + c)%9901;
        b = tmp_b;
        c = tmp_c;
	}
	int sum = (a + b) % 9901;
	sum = (sum + c) % 9901;
	printf("%d", sum);
}

 

풀이 : 다이나믹 프로그래밍

 

이전 층에 사자가 없다면 : 다음 층에는 사자가 없을수도, 왼쪽이나 오른쪽에 있을 수 있으며

이전 층에 사자가 왼쪽이면 : 다음 층에는 사자가 없을수도, 또는 오른쪽에 있을 수 있으며

이전 층에 사자가 오른쪽이면 : 다음 층에는 사자가 없을수도, 또는 왼쪽에 있을수 있습니다.

 

이를 다이나믹 프로그래밍을 이용하여 해결 할 수 있습니다.

 

배열을 만들어도 되나

변수 만을 이용해서도 풀이할 수 있습니다.

 

	없음	왼쪽	오른쪽
1칸	1	1	1
2칸	3	2	2
3칸	7	5	5
4칸	17	12	12

고로 4칸일때의 사자 배치의 경우의 수는 41 입니다.

 

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

1309번: 동물원