====== 2×n 타일링 2 ======

===== 풀이 =====
  * [[ps:problems:boj:11726]]의 변형. 2x2 블럭이 추가되었다.
  * 이제 2xn크기를 채우는 방법은 아래의 세가지 경우로 나뉜다
    * 2x(n-1) 을 채우고 2x1 블럭을 마지막에 붙이는 방법
    * 2x(n-2) 을 채우고 1x2 블럭 두개를 마지막에 붙이는 방법
    * 2x(n-2) 을 채우고 2x2 블럭을 마지막에 붙이는 방법
  * 점화식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-2] = 1*DP[n-1] + 2*DP[n-2]
  * 그냥 O(n)에 계산해도 되고, [[ps:선형_점화식#상수계수의 선형 점화식]]을 행렬곱으로 푸는 방법을 이용해서 O(logn)에 계산할수도 있다. n이 크지 않아서 실제 시간은 O(n)방법이 더 빨리 돌아가는것 같다


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11727. 2×n 타일링 2".

- Problem link: https://www.acmicpc.net/problem/11727
- Solution link: http://www.teferi.net/ps/problems/boj/11727

Tags: [DP] [LinearHomogeneousRecurrence]
"""

from teflib import combinatorics

MOD = 10007


def main():
    n = int(input())
    print(combinatorics.linear_homogeneous_recurrence([1, 2], [1, 1], n, MOD))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#linear_homogeneous_recurrence|teflib.combinatorics.linear_homogeneous_recurrence]]

{{tag>BOJ ps:problems:boj:실버_3}}