11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
n = int(input())
dp = [0]*(n+1)
dp[1] = 1
if n>=2:
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
print(dp[n] % 10007)
가로 길이를 1과 2의 합으로 나타낼 수 있는 경우의 수
f(n) = f(n-2) + f(n-1)