백준 11712번 : 2×n 타일링 2 (Python)

문제 : www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

풀이

기본적으로 타일을 나누어야 할 단위는 2*2 모양이다.

2*2 크기에 타일링이 가능한 경우의 수는 3이다.

하지만 이 경우 1*2 + 2*_인 경우만 고려되고

2*_ + 1*2인 위 그림과 같은 경우를 고려하지 못한다. 따라서 위 경우는 2가지가 가능하므로 n-3의 경우의 수에  2를 곱한값을 더해준다.

 

n = int(input())

dp = [0, 1, 3, 5]

for i in range(4, n+1):
    dp.append((dp[i-3]*2 + dp[i-2]*3)%10007)

print(dp[n])