동물원

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

틀린 풀이

• 동물 수에 따라 식을 세우려고 함

    d[1] : 동물 한 마리 들어갔을 때 경우의 수
  

  ​ d[2] : 동물 두 마리 들어갔을 때 경우의 수
  ​ …

• 이런식으로 하면 d[n-1] 과 d[n] 을 연결시키기가 어려움

옳은 풀이

• n-1 번째 줄 까지 우리에 맞게 들어갔다고 보고

• n 번째 줄에 어떻게 올 수 있는지 고려해야함

  • d[n][0] : n 번째 줄에 왼쪽만 사자가 들어감
    • n-1번째 줄에 오른쪽만 들어가거나, 아예 안들어감
  • d[n][1] : n 번째 줄에 오른쪽만 사자가 들어감
    • n-1번째 줄에 왼쪽만 들어가거나, 아예 안들어감
  • d[n][2] : n 번째 줄에 안들어감
    • n-1번째 줄에 오른쪽만 들어가거나, 왼쪽만 들어가거나, 아예 안들어감