백준 python 파이썬 11726 파이썬 2xn 타일링

백준 링크:https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

초반에 문제 이해를 잘못해서 꽤 시간이 오래 걸려버렸다.

2xn 도형과 nx2 도형을 전부 포함해서 이상한 결과값만 나와서 2xn의 도형만 맞는 값이 나왔다.

그림판으로 대충 그려본 경우의 수이다. 그림판으로 대충 끄적여서 퀄리티는 좀...

차례대로 [1,2,3,5] 이고 5개일 경우에도 8개가 나왔다.

[n-1] + [n-2] = [n] 의 값이 나오기에 dp에 적용시켰다.

 

 

풀이코드

n=int(input())
dp=[0,1,2]
for i in range(3,n+1):
    dp.append(dp[i-1]+dp[i-2])
print(dp[n]%10007)