[백준/Python] 2×n 타일링

문제

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

문제 요약

2 × n 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수를 출력한다.

 

2 × 5 크기의 직사각형을 채운 한 가지 방법

---

코드

n = int(input())

dp = [0] * (1001)
# dp[i]는 i번째 칸까지 1*2, 2*1 타일로 채우는 방법의 수

dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007

print(dp[n])

---

코드 설명

2 × n 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수

 

= 2 × (n - 1) 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수 +  2 × (n - 2) 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수

 

1) 2 × (n - 1) 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법에  2 × 1 타일 1개를 붙인 방법

 

2)  2 × (n - 2) 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법에 1 × 2 타일 2개를 붙인 방법

 

< 그림 출처 >

https://assb.tistory.com/entry/%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81

백준 11726번: 2xn 타일링