프로그래머스 lv2 3xN 타일링

문제 링크

3xN 타일링

풀이

• 2 x N 타일링에 이은 3 버전이고, 조금 더 대가리가 아프다.
• 직접 그려보면 홀수로 들어오면 경우의 수가 0인 것을 알 수 있다.
• 규칙성을 찾다보니...다음과 같은 점화식을 확인할 수 있다.

  f(n) = f(n-2) * 3 + ( f(n - 4) * 2 + ... + f(0) * 2) )

• 위와 같은 규칙으로 코드를 짜면된다.

코드

class Solution {
    public int solution(int n) {
        return threeTilingDP(n);
    }
    
    public int threeTilingDP(int n) {
        // 홀수의 경우에는 경우의 수가 0이 나온다.
        if (n % 2 == 1) return 0;
        long[] tile = new long[n + 1];
        tile[0] = 1;
        tile[2] = 3;

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

        return (int)tile[n];
    }
}

소감

• 규칙성 찾기 대실패