파이썬에서 2 x 1 도미노로 3 x n 상자를 채울 수 있는 방법의 수를 세는 프로그램

<시간/>

숫자 n이 있다고 가정하고 (3 x n) 블록을 1 x 2 도미노로 채울 수 있는 방법의 수를 찾아야 합니다. 필요할 때 도미노를 회전시킬 수 있습니다. 대답이 매우 크면 이 모드를 10^9 + 7로 반환합니다.

따라서 입력이 n =4와 같으면 출력은 11이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m =10^9 + 7
n이 홀수이면
- 0을 반환
cs :=1, OS :=0
2~n 범위의 i에 대해 2만큼 증가, do
- cs :=3 * cs + os
- os :=2 * cs + os
cs 모드 m 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n % 2 == 1:
         return 0
      cs = 1
      os = 0
      for i in range(2, n + 1, 2):
         cs, os = (3 * cs + os, 2 * cs + os,)
      return cs % m
ob = Solution()
n = 4
print(ob.solve(n))