✅ DP

문제

링크

1. 문제 접근 및 해결 로직

지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력하라는거 보니 경우의 수가 굉장히 많다는걸 예상할 수 있다.
따라서 완전탐색으로는 풀 수 없어 DP를 생각해봤다.

00 과 1 타일을 사용하기 때문에 n번째 타일은
1. (n-2)에 0 -> (n-1)도 0 -> (n) 은 1 만 가능
=> (n-2)에 의해 결정
2. (n-2)에 1 -> (n-1)은 0 or 1 둘 다 가능 -> (n)은 n-1에 무엇을 놓았느냐에 따라 결정
=> (n-1)에 의해 결정

따라서 n번째 타일은 n-2에 의해 결정되는 경우가 1가지, n-1에 의해 결정되는 경우가 1 가지 있다.

• 정의
  $f(N)$ : 만들 수 있는 길이가 N인 모든 2진 수열의 개수
• 구하는 답
  $f(N)$
• 초기값
  $f(1)=1$
  $f(2)=2$
• 점화식
  $f(N)=f(N-1)+f(N-2)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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