파이썬(Python) 코테 대비 DP : 백준 11726번 2xn 타일링

[시작 체크 리스트]

1. 1시간 지났으나 발상 불가 또는 아예 다른 길
2. 코드 50% 정도 완성
3. 1시간 보다 더 걸려서 코드 완성
4. 코드는 다 돌아가는데 효율성에서 걸림
5. 코드 완성

[완료 후 체크 리스트]

1. 아예 모르겠음
2. 중간 정도 이해함
3. 완벽히 이해함

[첨언]

그냥 11727번 공부하러 가자

1. 발상

n번째의 타일링을 하는 방법에는
1. n-1 번째에 2 * 1 타일링 1번
2. n-2 번째에 1 * 2 타일링 2번 해주기

점화식은 dp[n]=dp[n-1]+dp[n-2]

2. 코드

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)

(출처 : https://www.acmicpc.net/problem/11726)