[프로그래머스/파이썬] 3 x n 타일링

 

 

나의 풀이

def solution(n):
    if n % 2:
        return 0

    k = 1000000007
    n //= 2
    dp = [3, 11]

    if n > 3:
        for _ in range(n - 2):
            dp.append((dp[-1] * 4 - dp[-2] + k) % k)

    return dp[-1]

 - 홀수일때 불가하니 0

 - 짝수일때만 비교해서 dp로 해결

 - 규칙 구하는게 어려웠던 문제

 

 

 

배열 안쓰는 풀이

def solution(n):
    if n % 2:
        return 0
    front = back = 1
    for _ in range(n//2):
        front, back = back, (4*back - front) % 1000000007
    return back