[Python][프로그래머스][Level4] 3xn 타일링

[Python][프로그래머스][Level4] 3xn 타일링

코드

def solution(n):
    answer=[1]*(n//2+1)
    for i in range(1,n//2+1):
        answer[i]=(3*answer[i-1]+2*sum(answer[:i-1]))%1000000007
    return answer[n//2] if n%2==0 else 0

점화식을 구하는 문제다.

일단 가로 길이가 홀 수이면 만들 수 없으므로 0이다.

따라서 배열은 1/2 만 선언해도 된다.

가로 길이가 2일 때는 3이다.

가로 길이가 4일 때는 3*3 + 2 = 11이다.

가로 길이가 6일 때는 11*3 + 8 = 41이다.

이렇게 구하다 보면

answer[i]=3answer[i-1]+2sum(answer[:i-1]) 인 것을 알 수 있다.