프로그래머스 - 아방가르드 타일링

프로그래머스 - 아방가르드 타일링

주어진 세 종류의 타일로 n x 3 직사각형을 채우는 문제입니다. 흔한 dp 문제 유형같지만 타일 종류가 좀 특이해서 경우의 수가 많이 나옵니다.

저는 우선 n x 3을 왼쪽 m x 3과 오른쪽 k x 3인 직사각형(m + k = n) 둘로 쪼개는 아이디어를 생각했습니다. 오른쪽 더 이상 쪼갤 수 없는 k x 3을 만들 수 있는 k의 종류별로 각 dp[m]을 곱하면 되겠다고 생각했습니다.

난점은 k의 종류에 제한이 없다는 것입니다.

그래서 결국

dp[i] = dp[i-1] + dp[i-2] * 2 + dp[i-3] * 5 + dp[i-4] * 2 + dp[i-5] * 2 + dp[i-6] * 4 ... 계수 2,2,4 반복

이라는 무한급수를 얻습니다. 어떤 상수 k에 대해 dp[k]의 계수는 i를 3으로 나눈 나머지에 따라 2가 되기도 하고 4가 되기도 합니다. patternsOfFourTwo 라는 array에 나머지와 계수에 따른 dp누적합들을 갱신합니다. 이 과정에 약간의 노동이 필요했습니다.

그러나 하단에 더 좋은 풀이가 있습니다.

class Solution {
    public int solution(int n) {
        long[] base = new long[4];
        long[] dp = new long[100_001];
        
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 3;
        dp[3] = 10;
        base[0] = 1;
        base[1] = 1;
        base[2] = 2;
        base[3] = 5;
   
        // save the sum of dp[] for cases
        long[] patternsOfFourTwo = new long[6];
        
        for (int i = 4; i <= n; i++) {
            long four = 0;
            long two = 0;
            
            for (int j = 1; j < 4; j++) {
                dp[i] += dp[i - j] * base[j];
            }
            
            if (i > 3) {
                
                if (i % 3 == 1) {
                    patternsOfFourTwo[0] += dp[i - 4];
                    patternsOfFourTwo[2] += dp[i - 4];
                    patternsOfFourTwo[5] += dp[i - 4];

                    four = patternsOfFourTwo[1];
                    two = patternsOfFourTwo[0];
                } else if (i % 3 == 2) {
                    patternsOfFourTwo[1] += dp[i - 4];
                    patternsOfFourTwo[2] += dp[i - 4];
                    patternsOfFourTwo[4] += dp[i - 4];

                    four = patternsOfFourTwo[3];
                    two = patternsOfFourTwo[2];
                } else {
                    patternsOfFourTwo[0] += dp[i - 4];
                    patternsOfFourTwo[3] += dp[i - 4];
                    patternsOfFourTwo[4] += dp[i - 4];

                    four = patternsOfFourTwo[5];
                    two = patternsOfFourTwo[4];
                }
                
            }
            
            dp[i] += four * 4 + two * 2;
            dp[i] %= 1_000_000_007;
        }
        
        return (int) dp[n];
    }
}

 


프로그래머스에서 Seungrae라는 닉네임을 쓰시는 분께서는 더 좋은 아이디어로 훨씬 더 짧게 푸셨습니다.

dp[i] = dp[i-1] + dp[i-2] * 2 + dp[i-3] * 5 + dp[i-4] * 2 + dp[i-5] * 2 + dp[i-6] * 4 ... 계수 2,2,4 반복

에서 i에 i - 3 을 대입합니다.

dp[i-3] = dp[i-4] + dp[i-5] * 2 + dp[i-6] * 5 + dp[i-7] * 2 + dp[i-8] * 2 + dp[i-9] * 4 ... 계수 2,2,4 반복

두 식을 빼면

dp[i] - dp[i-3] = dp[i-1] + dp[i-2] * 2 + dp[i-3] * 5 +dp[i-4] - dp[i-6]

가 되어 무한급수가 사라집니다.

Seungrae님의 코드

class Solution {
    public int solution(int n) {
        int MOD = 1000000007;
        long[] dp = new long[100001];
        dp[0] = 1;
        dp[1] = 1; 
        dp[2] = 3;
        dp[3] = 10;
        dp[4] = 23;
        dp[5] = dp[4] + dp[3] * 2 + dp[2] * 5 + dp[1] * 2 + dp[0] * 2;

        for(int i = 6; i <= n; i++){
           dp[i] = (dp[i-1] + (dp[i-2] * 2) % MOD + (dp[i-3] * 6) % MOD + dp[i-4] % MOD - dp[i-6] % MOD + MOD) % MOD;
        }
        return (int)(dp[n] % MOD);
    }
}