[백준] 11727 - 2xn 타일링 2 in 파이썬

문제 출처

11727번: 2×n 타일링 2

 

문제

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

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

 

입력

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

출력

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

---

문제 풀이

규칙을 찾으면 되는 문제였다.

위와 같이 2x4 타일링까지 찾아본 결과,

 

N >= 3 일 때, 2xN 타일링은 다음과 같은 규칙을 갖는다.

1. 2*(N-1) 타일링에 2*1 타일을 하나 붙인다.
2. 2*(N-2) 타일링에 1*2 타일을 두 개 붙인다.
3. 2*(N-2) 타일링에 2*2 을 하나 붙인다.

따라서, DP 식은 dp[n] = dp[n-1] + 2*(dp[n-2]) 이다.

 

작성 코드

import sys
input = sys.stdin.readline

dp = [0, 1, 3]
for i in range(3, 1001):
  dp.append((dp[i-1] + dp[i-2]*2) % 10007)
n = int(input())
print(dp[n])