[프로그래머스][JAVA] 3 x n 타일링

링크

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

프로그래머스

 

설명

각 단계마다 이전 단계의 경우의 수에 영향을 받으므로 Bottom-up 방식의 DP 문제라고 판단할 수 있습니다.

 

N = 2 일 때는 이렇게 기본 타입 3개 나올 것입니다.

 

N = 4 라면 (3 * 3) +  2 = 11개 나올 것입니다.

 

아래 그림은 기본 타입 경우의 수 3개 * 3개 중 1개 입니다.

 

아래 그림은 특수 타입 경우의 수 2개 입니다.

 

따라서 3(2개 블럭을 붙이는 경우의 수) * 3(기본 타입 경우의 수, N=2일때 경우의 수) + 2 (특수 타입 경우의 수) = 11 이 됩니다.

 

N = 6 일 때는 이러한 비슷한 과정을 거쳐서 (3 * 11) + (2 * 3) + (2)  = 41이 나올 것입니다.

기본 타입 3 * (11) = 33개

일반적 모양입니다.

 

거기에 아까 있었던 N=4 특수 타입에 있던 것도 이제 포함이 됩니다.

 

전체적으로보면 이런 느낌입니다.

 

특수 타입 2 * (3) = 6개

N=2에 아까 N=4에서 봤던 특수 타입을 뒤에 붙일 수 있습니다. 이는 기본 타입에 붙어있는 모양과는 다릅니다.

 

새로 생기는 특수 타입 2개

 

이렇게 

33 + 6 + 2 = 41개가 됩니다.

 

N=8이후로도 비슷하게 진행이되므로 점화식으로 표현할 수 있습니다.

 

점화식
F(N) = 3 * F(N-2) + (2 * F(N-4) + 2 * F(N-6) + .... + 2 * F(0) )

아래로 저는 해석하였습니다.

F(N) (이번 단계 경우의 수) =
3 * F(N-2) (기본 타입 경우의 수 * 전 단계의 전체 경우의 수)
+ (2 * F(N-4) + 2 * F(N-6) + .... + 2 * F(0) ) (특수 타입 경우의 수 = 전전 단계의 특수 타입을 뒤로 붙이는 경우의 수 + 이번 단계의 특수 타입 경우의 수)

 

감상

점화식을 생각해내기 어려워서 풀지 못했던 문제였습니다.

항상 이런 문제는 새로운 인사이트를 주는 것 같습니다 :)

풀이

class Solution {
    public int solution(int n) {
        int MOD = 1_000_000_007;
        if (n==0) {
            return 1;
        }
        
        if (n%2 == 1) {
            return 0;
        }
        
        if (n == 2) {
            return 3;
        }
        
        long[] dp = new long[5001];
        dp[0] = 1;
        dp[2] = 3;
        for (int i=4; i <= n; i += 2) {
            // 이전 것에서 3가지 경우의 수
            dp[i] = 3 * dp[i-2] % MOD;
            for (int j=i-4; j>=0; j-= 2) {
                // 라인에 걸치는 2가지 경우의 수들
                dp[i] += 2 * dp[j] % MOD;
            }
        }
        
        return (int) (dp[n] % MOD);
    }
}​