[백준] 1309번 : 동물원

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

1309번: 동물원

 

---

문제 : 

가로로 2칸, 세로로 N칸인 동물원에서 사자를 이웃하지 않고 배치할 수 있는 경우의 수를 구하는 문제이다. 

 

 

풀이: 다이나믹 프로그래밍 (DP)

 

임의의 층에 사자를 배치할 수 있는 방법은 총 3가지 이다. 

 

1. 두 칸 모두 사자가 없는 경우 => 0이라고 칭함

2. 왼쪽에만 사자가 있는 경우 => 1이라고 칭함

3. 오른쪽에만 사자가 있는 경우 => 2라고 칭함

 

1번 두 칸 모두 사자가 없는 경우는

이전 칸에 어떻게 사자를 배치하더라도 구애받지 않는다. 

 

d[n][0] = d[n-1][0] + d[n-1][1] + dn[n-1][2]

 

 

2번 왼쪽에만 사자가 있는 경우는

이전 줄에 모두 사자가 없거나, 사자가 오른쪽에 배치되어야 가능한 구조이다. 

 

d[n][1] = d[n-1][0] + d[n-1][2]

 

 

3번 오른쪽에만 사자가 있는 경우는

이전 줄에 모두 사자가 없거나, 사자가 왼쪽에 배치되어야 가능하다. 

 

d[n][2] = d[n-1][0] + d[n-1][1]

 

 

초기 사자의 경우의 수는 모두 1로 시작해서 DP를 실행하면 된다. 

 

 

중간에 %9901 연산이 없으면 메모리가 부족하므로 꼭 넣어주어야한다.