[Programmers] 3xn 타일링

 

DP

문제링크

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

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

 

package programmers.level4;

public class nx3_타일링 {
	
	public long solution(int n) {
        
        long[] dp = new long[n+1];
        
        dp[0] = 1;
        dp[2] = 3;
        
        if(n > 2) {
        	for(int i = 4 ; i <= n ; i += 2) {
        		dp[i] = dp[i-2] * 3;
        		for(int j = 0 ; j < i-2 ; j += 2) {
        			dp[i] += dp[j] * 2;
        		}
                dp[i] %= 1000000007;
        	}
        }
        return dp[n];
    }
	
}