[programmers] 3 x n 타일링

10 May 2023 in Algorithm on Algorithm

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

class Solution {
    public int solution(int n) {
        long[] dp = new long[n+1];
        long mod = 1000000007L;

        if(n%2 != 0) return 0;

        dp[0] = 1L;
        dp[2] = 3L;
        dp[4] = 11L;

        for(int i = 6 ; i <= n ; i = i+2 ){
            dp[i] = (dp[i-2] * 3) % mod;
            for(int j = i-4 ; j >= 0 ; j = j-2){
                dp[i] = (dp[i] + (dp[j] * 2)% mod) % mod;
            }
        }

        return (int) dp[n];
    }
}