[파이썬(Python)] 백준 11727번 2×n 타일링 2

 

 

백준 11727번: 2×n 타일링 2

문제 바로 가기

---

📌 문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

 

 

 

 

📝 아이디어

 

이 문제는 $2 \times n$ 크기의 직사각형을 $1 \times 2$, $2 \times 1$, $2 \times 2$ 타일로 채우는 방법의 수를 구하는 것입니다. 

 

아래의 그림처럼 $2 \times n$ 직사각형을 채우는 방법은 마지막 타일의 배치 방식에 따라 결정됩니다. 

 

 

1. 마지막 타일을 $2 \times 1$ 타일로 채우는 경우

• 남는 부분은 $2 \times (n - 1)$ 크기의 직사각형입니다.
• 따라서 $dp[n]$은 $dp[n-1]$로부터 결정됩니다.

 

2. 마지막 타일을 $1 \times 2$ 타일 2개로 채우는 경우

• 남는 부분은 $2 \times (n-2)$ 크기의 직사각형입니다.
• 따라서 $dp[n]$은 $dp[n-2]$로부터 결정됩니다.

 

3. 마지막 타일을 $2 \times 2$ 타일로 채우는 경우

• 남는 부분은 $2 \times (n-2)$ 크기의 직사각형입니다.
• 따라서 $dp[n]$은 $dp[n-2]$로부터 결정됩니다.

 

세 가지 경우를 합치면 다음과 같은 점화식이 도출됩니다.

$$dp[n] = dp[n-1] + 2 \times dp[n-2]$$ 

 

 

 

 

👩‍💻 나의 답안

n = int(input())

dp = [0] * (n+1)
dp[1] = 1

if n > 1:
    dp[2] = 3

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

print(dp[n])