백준 11727번 2xn 타일링 2

저번 문제와 거의 유사하다

https://idol-kotori.tistory.com/10

백준 11726번

똑같이 그림그려보면

이런식으로 3가지 경우로 나눠볼수있다

따라서

 

초기값은

n==1 return 1 n==2 return 3

 

점화식은 전과 동일하게

d[n]=d[n-1]+d[n-2]

라고 생각했었지만 d[n-2]가 2개 존재하기때문에 2번 더해줘야한다

d[n]=d[n-1]+d[n-2] +d[n-2]

이 형태가 되어야한다

 

import sys

n=int(sys.stdin.readline().rstrip())

data=[0]*(n+1)

def dp(n):
    if data[n]!=0:
        return data[n]
    if n==1:
        data[n]=1
        return 1
    elif n==2:
        data[n]=3
        return 3
    data[n]=(dp(n-1)+dp(n-2)+dp(n-2))%10007
    return data[n]

print(dp(n))

 

저번 문제랑은 다르게 살짝 더 깔끔하게 수정해봤다