[Python] 11726번 2xn 타일링

✏️ 문제

 

문제 파악

n이 1일 때부터 4일 때까지 직접 해보면 다음과 같이 나온다.

여기서 점화식을 찾을 수 있는데 피보나치 수열과 같다는 것을 알 수 있다.

점화식을 기준으로 코드를 짜면 쉽게 풀 수 있다!

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

n = int(input())
ary = [0, 1, 2, 3]

for i in range(4, n+1):
  ary.append(ary[i-1] + ary[i-2])

print(ary[n] % 10007)