[Python] 11727번 2xn 타일링 2

✏️ 문제

 

문제 파악

11726번 2xn 타일 의 업그레이드(?)된 문제이다. 11726번 문제와 같이 점화식을 찾는 것이 중요한데 시간 좀 걸렸다... 그래도 풀었으니..!

직접 n이 1, 2, 3, 4 일 때 dp(n)의 값을 찾았을 때 1, 3, 5, 11이 나왔다.

n = 3일 때 dp(n) = 5인데 이는 dp(n-1) + dp(n-2) + dp(n-2) 의 값과 같은 것을 알 수 있다. 

이를 토대로 점화식은 dp(n) = dp(n-1) + (dp(n-2) * 2) 이다.

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

n = int(input())
dp = [0, 1, 3, 5, 11]

for i in range(len(dp), n+1):
  dp.append(dp[i-1] + dp[i-2]*2)

print(dp[n] % 10007)