[Python] 백준 11726. 2xn 타일링

 

문제 링크

 

 

풀이

n = 1 일 때 2x1 타일 하나,

n = 2 일 때 2x1 타일 둘 혹은 1x2 타일 둘

즉 dp[1], dp[2] = 1, 2

dp[3]부터는 이전 기록해뒀던 누적값들을 더해나간다

이를 점화식으로 세우면 dp[i] = dp[i-2] + dp[i-1]

 

코드

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