https://www.acmicpc.net/problem/11726

초고

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

dp 를 이용하는 문제.

• 2xi 직사각형의 마지막 부분을 보고 이 부분이 채워질 경우의 수를 확인한다.
• 하나의 2x1 타일(마저 채워야할 타일은 2x(i-1) 직사각형이다)
• 두 개의 1x2 타일(마저 채워야할 타일은 2x(i-2) 직사각형이다)

dp[i] = dp[i-1] + dp[i-2]