프로그래머스 - 3 x n 타일링

문제

풀이

• 가로의 길이가 홀수인 경우의 수는 0
• n이 2씩 커질 때마다 어떤 규칙이 생기는지 확인
• n일 때 생기는 새로운 규칙을 더해주어야 한다.
• 그리고 n보다 작은 값에서 새롭게 생겼던 규칙들의 경우의 수들을 2씩 곱해서 더해줘야함

유의할 점

• dp문제인 걸 알지만 그 규칙을 찾아내는 게 너무 어렵다

코드

class Solution {
    public int solution(int n) {
        long[] dp = new long[n+1]; 
        dp[2]= 3; 
        dp[4] = 3*dp[2]+ 2; 
        
        for(int k=6; k<=n; k+=2){
            long sum =0; 
            for(int i=1; i<=k/2-2; i++)  sum+=dp[2*i];
            
            dp[k] = (dp[k-2] * 3 + 2*sum +2)%1000000007; 
        }
        if(n%2==1) return 0; 
        else return (int)dp[n]; 
    }
}