2×n 타일링

• 기초적인 DP문제. 그래서 변형 문제도 많다.
  • 2×2 타일을 추가하면 2×n 타일링 2 이 된다.
  • 여기에서 채워야 하는 칸을 3xn으로 바꾸면 타일 채우기 이 된다.
  • 이 문제 자체는 프로그래머즈의 2 x n 타일링과 동일한 문제이다
• 2xn을 채우는 방법은 두가지로 나뉜다
  • 2x(n-1)을 채우고, 마지막에 2×1 타일을 붙이는 방법
  • 2x(n-2)을 채우고, 마지막에 1×2 타일 두개를 붙이는 방법
• 따라서 점화식은 dp[n] = dp[n-2] + dp[n-1]처럼 되고, 이것은 피보나치 수 (Fibonacci numbers)의 점화식이므로, 답도 피보나치 수열이 된다.
• n+1번째 피보나치 수 (Fibonacci numbers)를 구하면 되므로 시간복잡도는 O(logn).

"""Solution code for "BOJ 11726. 2×n 타일링".

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 10007


def main():
    n = int(input())
    print(combinatorics.fibonacci(n + 1, MOD))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.fibonacci