[백준/Python] 11726번. 2×n 타일링

문제

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

 

 

풀이

일단 직접 그려보자.

 

규칙이 보일듯 말듯 하다.

 

각 인덱스에서 n-1 인덱스에 등장했던 모양을 포함하는 수와
새로 등장한 모양의 수를 세서 더한 값은 다음과 같다.

 

그렇다. 각 색상은 이전의 두 숫자의 합이 다음 숫자가 되는 피보나치 수열을 따르고 있다.
이제 정답 인덱스의 값을 구해서 10007로 나눈 나머지를 출력하면 된다.

 

 

 

정답 코드

n = int(input())
dp = [1, 2]
while n > len(dp):
    dp.append(dp[-1] + dp[-2])
print(dp[n - 1] % 10007)

 

점화식: dp[n] = dp[n-1] + dp[n-2]