[백준] 11727번 2xn 타일링 2 (Python)

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

📌 문제

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

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

 

📌 입력

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

 

📌 출력

 

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

 

---

📌 풀이 방식 

총 2x1, 1x2, 2x2 세 가지의 타일을 사용할 수 있는데요. 

 

 

 

n = 1 일 때는 1x2 타일 로 총 1가지 경우의 수로 나타낼 수 있고

n = 2 일 때는 1x2 2개 / 2x1 2개 / 2x2 1개 로 총 3가지의 경우의 수로 나타낼 수 있습니다. 

n 이 2일 때까지는 그냥 머리로 계산해서 구할 수 있는데요. 

그렇다면 n = 3 일 때 경우의 수는 어떻게 될까요 ?

 

이렇게 총 다섯가지 경우가 됩니다. 

혹시 해당 경우를 보고 규칙을 구할 수 있을까요 ? (힌트는 블록 색에 있습니다) 

n = 1 의 경우의 수에 2x1 2개랑 2x2 1개가 덧붙여졌고, 

n = 2 의 경우의 수에 1x2 타일 하나가 붙여져서 총 5가지의 경우의 수가 나온 걸 알 수 있습니다. 

 

아하 그러면 n 의 경우의 수를 구하려면 

n - 2 의 블록에는 2x1 2개랑 2x2 1개 로 총 2개를 붙이면 되고, 

n - 1 의 블록에는 1x2 로 총 1개를 붙이면 되겠네요. 

 

해당 식을 나타내보면 이렇습니다. 

n - 2 의 개수 * 2 + n - 1 의 개수 

 

해당 식을 이용해서 n = 4 를 구해보겠습니다. 

그럼 이제 보이시나요 ?

 

주황색 블록이 n-2 에서 가져온 블록이고, 

초록색 블록이 n-1 에서 가져온 블록입니다. 

 

주황색 블록들 뒤에는 2x1 2개랑 2x2 1개 가 붙었고,

초록색 블록들 뒤에는 1x2 가 붙어서 n = 4 일 때의 경우의 수는 총 11개로 나타낼 수 있습니다. 

이런 방식을 계속 반복해주면 됩니다

10,007로 나눈 나머지를 출력해야하는 거 잊지 마시구요 !!

 

📌 코드

n = int(input())
dp = [0 for _ in range(max(n, 2))]

dp[0] = 1
dp[1] = 3

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

print(dp[n-1] % 10007)