프로그래머스 Lv.4) 3xn 타일링

3xn 타일링

프로그래머스

풀이

타일링 시리즈 문제로 DP 문제이다. 하지만, 점화식 세우는데 애를 먹었다. 

우선, 홀수의 경우 타일을 채울 수 없다는 것과 dp[n] = dp[n-2]*3 부분까지는 쉽게 세울 수 있었다. n이 2씩 증가할 때마다 새롭게 생기는 3x2의 직사각형 부분을 채우는 경우의 수가 3가지기 때문에 이 전보다 3배의 경우의 수가 더 생긴다.

n이 2 증가할 때마다 채울 수 있는 경우의 수 3가지

이해하기 힘들었던 부분은 n이 4마다 새롭게 생기는 2가지 경우의 수였다.

n이 4 증가할 때마다 채울 수 있는 경우의 수 2가지

n이 4 증가할 때마다 생기는 이 부분 때문에 많은 고민을 하게했고, 다른 분들이 포스팅하신 점화식을 참고하게 되었다.. ㅠ

하... 아무튼 나는 이 부분에 대해서 새롭게 변수를 만들어 주기보다는 dp의 홀수 idx는 쓰지 않기 때문에 홀수 idx에 저장했다.

즉, n=4일 때 추가적으로 생기는 이 부분을 dp[3]에 넣어주고, n=6일 때 이 부분을 dp[5]에 넣어주는 식으로 이용했다.

 

최종적으로,

dp[n] = dp[n-2]*3 + dp[n-3](Additional Point) + dp[n-4]*2 이런식의 점화식이 세워졌다.

 <- dp[n-3]은 홀수 번 째의 경우가 아님을 유의

 

코드

public class Tiling_12902 {
    public static void main(String[] args) {
        int n =5000;
        System.out.println(solution(n));
    }

    private static int solution(int n) {
        int answer =0;
        if(n ==2) {
            answer =3;
        } else if(n%2 ==0) {   // 짝수일 때만
            int div = 1000000007;
            long[] dp = new long[n+1];
            dp[1] = 2;
            dp[2] = 3;

            for(int i=4; i<=n; i+=2) {
                // 점화식
                dp[i] = dp[i-2]*3;
                dp[i-1] = dp[i-3] + dp[i-4]*2; // 홀수는 안쓰이기 때문에 add를 저장
                dp[i] += dp[i-1];
                dp[i] %= div;
            }
            answer = (int)dp[n];
        }

        return answer;
    }
}