[Programmers]

문제

n이 주어질 때, 세로가 3, 가로가 n인 타일로 만들 수 있는 경우의 수를 1000000007로 나눈 나머지를 구해라

 

원본

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

 

풀이

def solution(n):
    if n % 2 != 0: return 0
    
    idx = n // 2
    lst = [0, 3, 11]
    
    if idx < 3:
        return lst[idx]
    
    for i in range(3, idx+1):
        lst.append((3*lst[i-1] + 2*sum(lst[1:i-1]) + 2) % 1000000007)
    
    return lst[idx]