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

1. 문제와 예제

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

11727번: 2×n 타일링 2

묹제

예제

---

2. 전체 코드

# 입력 받기
n = int(input()) # 2xn 크기의 직사각형
lst = [0, 1, 3] # 채우는 방법 수 리스트

for _ in range(998):
    lst.append(lst[-1] + lst[-2]*2)

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

---

3. 코드 해설

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

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

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

3. 2x2 직사각형으로 사용하면 마찬가지로 2x(n-2) 직사각형을 채우는 가짓수와 같다.

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