도도의 정리함 도도의 정리함

문제를 읽고 일단 어떤 경우의 수가 가능할 지 생각을 해보았다. n = 1일 때, 즉 우리가 2칸일 때에 3개의 경우의 수가 있음을 쉽게 생각해 낼 수 있다: 사자가 없을 때, 첫번째 칸에 사자가 있을 때, 두번째 칸에 사자가 있을 때 n을 하나 늘리기 전에 현재 경우의 수가 어떠한 영향을 줄 수 있을 지 생각해보자. 만약에 제일 밑 칸이 빈칸이라면 n이 하나 늘어났을 때에 현재 제일 밑 칸 아래에 새로 생길 칸의 구성은 3가지다: 빈 칸, 왼쪽 칸에 사자, 오른쪽 칸에 사자. (두 칸 모두 사자가 존재할 수는 없다) 하지만 제일 밑 칸 중 한 칸에 사자가 있다면 새로운 두 칸의 구성은 2가지가 가능하다: 빈 칸 그리고 제일 밑 칸에 있는 사자와 붙어있지 않는 쪽 칸에 사자 n이 늘어날 때마다 새로 더해..