✅ DP

문제

링크

1. 문제 접근 및 해결 로직

마지막 숫자가 0으로 끝나면 다음 숫자로 0,1 모두 올 수 있고
마지막 숫자가 1로 끝나면 다음 숫자로 0만 올 수 있다.

$f(n,0)$ : 0으로 끝난 $n$자리 이친수의 개수
$f(n,1)$ : 1로 끝난 $n$자리 이친수의 개수
라고 하면,

$f(n,0)=f(n-1,0)+f(n-1,1)$
$f(n,1)=f(n-1,0)$
임을 알 수 있다.

• 정의
  $f(n,0)$ : 0으로 끝난 $n$자리 이친수의 개수
  $f(n,1)$ : 1로 끝난 $n$자리 이친수의 개수
• 구하는 답
  $f(n,0)+f(n,1)$
• 초기값
  $f(1,0)=0$
  $f(1,1)=1$
  $f(2,0)=1$
  $f(2,1)=0$
• 점화식
  $f(n,0)=f(n-1,0)+f(n-1,1)$
  $f(n,1)=f(n-1,0)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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