[백준] 11726번 2×n 타일링 - 파이썬(Python)

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

11726번: 2×n 타일링

문제

 

접근법

 

2부터 순서대로 나열을 해보니 피보나치 수열임을 확인

피보나치 수열은 arr[i]=arr[i-1]+arr[i-2]의 규칙을 갖고 있음.

 

피보나치 수열을 적용해 마지막 값까지 구하고, arr[n]을 10007로 나눈 나머지를 출력

 

 

코드

n=int(input())
arr=[0]*(n+1)

arr[1]=1

if n!=1:
    arr[2]=2
    
for i in range(3,n+1):
    arr[i]=arr[i-1]+arr[i-2]

print(arr[n]%10007)