11727 2xn 타일링 2

타일링 문제에서 업그레이드 한 버전

이번에도 똑같이 1~4까지의 타일들을 보고 점화식을 뽑아봤다.

 

1-> 1개

2-> 3개

3-> 5개

4-> 11개

이번에 n=4일때의 타일들을 봤는데, 기존의 3일때의 타일들에 1개씩 추가된것도 들어있지만, 2에서 추가된게 총 6개였다.

그래서 보니 3의 타일들x2개씩 더 추가가 된것을 확인했다.

그래서 식을  뽑아보면 dp[i]=dp[i-1]+dp[i-2]*2라는 식을 도출했다.

 

풀이

#n 입력
n=int(input())

dp=[0]*(n+1)
dp[1]=1
if n>=2:
  dp[2]=3
  for i in range(3,n+1):
    dp[i]=dp[i-1]+2*dp[i-2]
print(dp[n]%10007)