[백준 11727] 2×n 타일링 2 with Python

문제 링크

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

풀이

import sys

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

2 x n 직사각형을 채우는 경우의 수를 f(n)이라고 할 때 f(n)은 아래의 두 경우의 수의 합과 같다.

1. f(n-1)에 2 x 1 타일을 붙이는 경우

2. f(n-2)에 2 x 2 크기의 직사각형을 덧붙이는 경우

 

2번째 경우에서 2 x 2 크기의 직사각형을 채우는 방법은 2 x 1 타일 2개, 1 x 2 타일 2개, 2 x 2 타일 1개로 총 3가지가 있다. 그러나 2 x 1 타일 2개를 붙이는 방법은 1번 경우와 겹치기 때문에 여기서는 1 x 2 타일과 2 x 2 타일을 붙이는 총 2가지만을 고려한다.

 

따라서, 다음과 같은 점화식을 세울 수 있다.

 

f(n) = f(n-1) + f(n-2) x 2