[ 프로그래머스 ] #12902 : 3 x n 타일링 - JAVA

🔗 3 x n 타일링

🔎 점화식

$f(n) = f(n-2) * f(2) + f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2$

class Solution {
    static int MOD=1000000007;
    public int solution(int n) {
        long [] dp = new long [n+1];
        // 초기 값 
        dp[2] = 3;

        for(int i = 4; i <= n; i+=2){
            //(이전 경우 * dp[2] 인 경우 + 특수한 경우 2개
            dp[i] = dp[i-2]*dp[2] + 2;

            // dp 값 완성
            for(int j = 2; j <= i-4; j+=2) {
                dp[i] += dp[j]*2;    
            }

            dp[i] = dp[i]%MOD;
        }

        return (int)dp[n];
    }
}