3 x n 타일링

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

코딩테스트 연습 - 3 x n 타일링

 

파이썬

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

공간의 낭비가 있으니...

def solution(n):
    if n % 2 != 0:
        return 0
    a1, a2 = 3, 11
    if n == 2:
        return a1
    elif n == 4:
        return a2
    for i in range(n // 2 - 2):
        a2, a1 = (a2 * 4 - a1) % 1000000007, a2
    return a2

줄이면

def solution(n):
    if n % 2 != 0:
        return 0
    a1 = a2 = 1
    for i in range(n // 2):
        a2, a1 = (a2 * 4 - a1) % 1000000007, a2
    return a2