(Python/LV2) 3 x n 타일링

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/12902?language=python3 

프로그래머스

풀이:

def solution(n):
    dp = [0 for i in range(n+1)]
    dp[0],dp[2], = 1,3

    for i in range(4,n+1,2):
        dp[i] = (dp[i-2] * 4 - dp[i-4]) % 1000000007


    return dp[-1] if n % 2 == 0 else 0

 

f(0) 을 1로 해줬다.

점화식을 계산하는데 오래걸렸다. 3번째 경우의수 41까지 일단 찾아내고 공식을 구해봤더니 

내가 발견한 점화식은

f(i) = ( (f(i-2) * n) - f(i-4) ) % 1000000007

 

그리고 n이 홀수면 꽉 채워넣지 못하므로 0 을 리턴한다.