백준 11727 2xn 타일링 2

문제 : 11727

풀이 point

2xn 타일링에서 2x2 블럭 하나가 추가 된 버전이다.

이런식으로 N = 4일때 N=3일때 경우의 수에 (1x2)타일을 하나씩 더해주고, N=2일때 경우의 수에 (2x2, 2x1*2) 타일을 하나씩 더해주면된다.

N=3일때 경우의 수 + N=2일때 경우의 수x2 라는 수식을 얻을 수 있다.

풀이 코드

N = int(input())
dp = [0]*1001

dp[1] = 1
dp[2] = 3
dp[3] = 5

for i in range(4, N+1):
    dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007

print(dp[N])