https://www.acmicpc.net/problem/1309 DP를 사용 맨 위의 두 칸을 세 가지 경우로 나눈다- 공백: 두 칸에 아무도 없음- 좌: 왼쪽 칸에 사자 있음- 우: 오른쪽 칸에 사자 있음 만약 n이 1이라면위처럼 세 가지 경우가 있습니다 n이 2인 경우를 보겠습니다 그런데 아래 칸(파란색)의 경우의 수는n=1일 때의 경우의 수와 같습니다 즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다. dp 점화식으로 풀게 된다면# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른..
