Dynamic Programming(DP) - 2×n 타일링[11726]

n = int(input())

dp = [0, 1, 2]

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

이번 문제의 규칙을 찾다보면 피보나치 수열을 따른다는 것을 알 수 있다.

이것만 찾으면 큰 무리 없이 구할 수 있는 문제다.

 

n = 2

n = 3

n = 4

2+3 = 5

n = 5

3+5 = 8

n = 6

5+8 = 13