[알고리즘 일기 - 파이썬] 188. 2xn 타일링

문제 188. (2022-02-18)

 

11726번: 2×n 타일링

Baekjoon 11726. 2xn 타일링

[파이썬(python) - DP]

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

---

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

---

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

---

입력 예시

2

 

---

출력 예시

2

 

---

❧ 정답

🔎IDEA) dp - 피보나치 수열

점화식 설명

1. n = 1 일때는 세로타일 하나만 가능
2. n = 2 일때는 세로타일을 이어 붙인 것과, 가로타일을 이어 붙인 경우 총 2가지 가능
3. n = 3 일 때