✅ DP

문제

링크

1. 문제 접근 및 해결 로직

직사각형의 크기는 2x$n$로 정해져 있기 때문에
마지막 $(n-2)$ -> $(n-1)$ -> $(n)$ 순서대로 놓는다고 생각하자.

1. $(n-2)$ 에 1x2을 놓으면 $(n-1)$은 자동으로 결정되고 $(n)$ 도 자동으로 결정된다. -> 2x1
2. $(n-2)$ 에 2x1을 놓으면 $(n-1)$에 뭘 놓는지에 따라 $(n)$가 자동으로 결정된다.
3. $(n-2)$ 에 2x2을 놓으면 $(n-1)$은 자동으로 결정되고 $(n)$ 도 자동으로 결정된다. -> 2x1

정리하면 $(n)$은 $(n-2)$에 따라 자동으로 결정되는 경우가 2개,
$(n-1)$에 따라 자동으로 결정되는 경우가 1개이다.

따라서 점화식은 아래와 같다.

• 정의
  $f(n)$ : $n$까지 타일로 채우는 방법의 수
• 구하는 답
  $f(n)$
• 초기값
  $f(1)=1$
  $f(2)=3$
• 점화식
  $f(n)=2*f(n-2)+f(n-1)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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