11727번 Python

두번째 타일링 문제이다. 이번엔 2x2 타일이 하나 늘어났다. 예전에 풀었는데 이번엔 제대로 된 점화식을 찾아서 정리해보려고 한다.

 

일단 4까지는 손수 그림을 그리면서 갯수를 찾아냈다. f(4)는 특징이 하나 있다. 위 이미지의 f(4) 그림의 빨간색 부분은 f(3)에서 1x2 타일을 하나 더 붙인셈이다. 즉, f(3)의 갯수를 가지고 있다. 그리고 f(4)의 파란 부분을 보면 f(2)에서 존재하는 타일을 두 번씩 사용했다.

 

즉, 문제의 점화식은

f(i) = 2 * f(i - 2) + f(i - 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])

코드로 구성하면 이렇게 된다.