BaekJoon11726_2xN 타일링

문제

풀이

각 경우의 수들을 쭉 적어보면 i번째 때 필요 타일 개수는 i-1번째와 i-2번째의 필요 타일 개수를 합한 것과 같다는 규칙을 발견할 수 있다.

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(1001)]

dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3


for i in range(3, n+1):
    dp[i] = dp[i-2] + dp[i-1]   
    
print(dp[n]%10007)