백준 11727번(Python) : 2 x n 타일링 2

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

n 번째의 타일리을 위해서는 세가지 경우가 존재한다.

(1) n-1 번까지의 타일링 이후 2x1 타일을 붙이는 경우

(2) n-2 번까지의 타일링 이후 1x2 타일을 두개 붙이는 경우

(3) n-2 번까지의 타일링 이후 2x2 타일을 한개 붙이는 경우

 

그러므로 이러한 세가지 상황을 모든 경우의 수로 따져 코드를 작성해 보면 다음과 같다.

 

import sys
input = sys.stdin.readline

n = int(input())

d = [0,1,3]

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