12/19 3xn 타일링

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

2xn 타일링

제목만 보고 2xn 타일링을 확장한 문제여서 금방 풀거라고 생각했지만 생각보다 매우 어려워 다른 블로그의 힘을 빌렸다..

위의 그림처럼 일반화를 해보면 점화식은 다음과 같다. \(dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + ... + dp[2] * 2 + 2\)

내 풀이

def solution(n) :
    mod = 1000000007
    dp = [0 for _ in range(n + 1)]
    dp[2] = 3
    for i in range(4, n + 1, 2) :
        dp[i] = dp[i - 2] * 3 + 2
        for j in range(i - 4, -1, -2) :
            dp[i] += dp[j] * 2
		dp[i] = dp[i] % mod
	return dp[n]