[백준] 11726번 파이썬 (2xn 타일링)

1. 문제와 예제

(문제링크: https://www.acmicpc.net/problem/11726)

11726번: 2×n 타일링

문제

예제

---

2. 전체 코드

# 입력 받기
n = int(input()) # 2*n 크기의 직사각형
lst = [0, 1, 2]

# 피보나치 수열 리스트(길이 1001) 생성
for _ in range(998):
    lst.append(lst[-1]+lst[-2])

# 결과 출력하기
print(lst[n] % 10007)

---

3. 코드 해설

n을 늘려가면서 가짓수를 적다보니 피보나치 수열을 따른다는 것을 확인할 수 있었다. 왜 피보나치 수열을 따르게 되는 것일지 생각해보니 아래와 같이 정리할 수 있었다.

2x(n-1) 직사각형 우측에 2x1 직사각형을 하나 붙인다고 생각하고 가짓수가 어떻게 변하는지 생각해보면,

1. 2x1 직사각형을 2x1로 사용하면 2x(n-1) 직사각형을 채우는 가짓수와 같고

2. 2x1 직사각형을 포함하여 2x2 직사각형으로 사용하면 2x(n-2) 직사각형을 채우는 가짓수와 같다.

따라서 2xn 직사각형을 채우는 방법의 가짓수 = 2x(n-1) 가짓수 + 2x(n-2) 가짓수 이다.