11727번 Python

2xn 타일링 문제의 두번째 변형 문제이다. 이번에는 1x2, 2x1, 2x2 타일이 존재한다. 마찬가지로 직접 그림을 그려가보면서 점화식을 구해보는 것을 목표로 한다.

 

마찬가지로 총 2x4 직사각형까지의 타일을 모두 조합해보았고 다음과 같은 결과를 알 수 있었다. 이번에는 어떤 규칙이 보이는지, 그 규칙이 어떻게 그렇게 되는지 알아보겠다.

 

n의 경우에 n-1 타일을 1번씩 모두 사용했고 n-2 타일은 2번씩 사용한 것을 확인할 수 있다.

 

dp[n] = 2 * dp[n-2] + dp[n-1]

따라서 이것이 해당 문제의 점화식이라고 볼 수 있게 되는 것이다.

 

import sys

n = int(sys.stdin.readline())
dp = [0] * 1001

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

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

print(dp[n] % 10007)

코드로 나타내면 이런 형태가 될 것이다.