2×n 타일링 풀이

문제 링크: https://www.acmicpc.net/problem/11726

백준 알고리즘 기초 1/2 400에서 2번째 - 11726번 2×n 타일링를 풀어보았다.

 

풀이: 피보나치수열처럼 2*i 사각형을 채우는 경우의 수는 i-1과 i-2를 채우는 수의 합이다.

 

C++

 

Python

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

Java