[Python] 3 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12902

---

수가 너무 커 오버플로우가 발생할 경우를 방지하기 위해 모듈러 연산을 이용해 저장되는 값을 작게 만들어 저장한다.

모듈러 연산 분배법칙

cf. 나머지 모듈러 연산은 페르마의 소정리를 이용해 B의 역원인 B^-1 을 구해 곱하는 형식으로 구한다.

(ex: 4/3mod11 = 4*4 mod 11 = 16 mod 11 = 5 mod 11)

def solution(n):
    # 1. dp 정의 
    # dp[i] = 4*dp[i-2] - dp[i-4]
    dp = [0 for _ in range(n+1)]
    # 2. 초기값 채우기
    dp[0] = 1
    dp[2] = 3
    # 3. dp 테이블 채우기 (모듈러 연산의 분배법칙 이용)
    for i in range(4,n+1,2):
        dp[i] = ((4 * dp[i-2]%1000000007) - dp[i-4]%1000000007) % 1000000007
    return dp[n]