풀이

많이 풀어본 dp 문제이다.
점화식을 세우는 것이 관건이다.
풀이
전에 백준에서 같은 문제를 푼 적이 있다.

코드

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