2×n 타일링 2

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

"""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()

• Dependency: teflib.combinatorics.linear_homogeneous_recurrence