[파이썬] BOJ_11727(2*n 타일링 2)

문제

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

 

해설

 

이 문제는 dp문제로 규칙만 찾으면 쉽게 풀 수 있다.

 

처음엔 2*5까지 직접 정리해보고

dp[i] = dp[i-1] + dp[i-2] + (2*(i-2)-1) 인 줄 알았다.

그러나 백준 예제입력2만 해봐도 이게 아니란 걸 알 수 있다.

규칙 찾는데 약간 헤맸지만 자세히 보면

dp[i] = dp[i-1] + (dp[i-2]*2)규칙을 찾을 수 있다. 

 

dp[i-1]과 dp[i-2]를 알아내려면 최소한 dp[1], dp[2]는 미리 알아야하기에 따로 입력해놓고

반복문은 dp[3]부터 돌도록 하면 된다.

---

코드

 

-파이썬

#백준 11727(2*n 타일링 2)

n = int(input())

dp = [0]*1001
dp[1] = 1
dp[2] = 3

for i in range(3, 1001):
    dp[i] = dp[i-1] + (dp[i-2]*2)

print(dp[n] % 10007)