✅ DP

문제

링크

1. 문제 접근 및 해결 로직

인접한 칸에는 사자를 놓을 수 없으므로 한 행에는 최대 한마리의 사자만 놓을 수 있다.

이전 행에 사자를 두칸 중 어디에 놓았는지, 아니면 놓지 않았는지에 따라 이번 행에 놓을 위치가 정해진다.

이번 행에 사자를 놓는 경우의 수는 3가지 이다.
1. 아에 놓지 않는다.
2. 왼쪽에 놓는다.
3. 오른쪽에 놓는다.

• 정의
  $dp[n][0]$ : $n$ 번째 칸에 사자를 놓지 않은 경우의 수
  $dp[n][1]$ : $n$ 번째 칸에 사자를 왼쪽 칸에 놓은 경우의 수
  $dp[n][2]$ : $n$ 번째 칸에 사자를 오른쪽 칸에 놓은 경우의 수
• 구하는 답
  $dp[n][0]+dp[n][1]+dp[n][2]$
• 초기값
  $dp[1][0]=1$
  $dp[1][1]=1$
  $dp[1][2]=1$
• 점화식
  $dp[n][0]=dp[n-1][0]+dp[n-1][1]+dp[n-1][2]$
  $dp[n][1]=dp[n-1][0]+dp[n-1][2]$
  $dp[n][2]=dp[n-1][0]+dp[n-1][1]$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항