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

문제

링크

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

가로의 길이 n은 5,000이하의 자연수 입니다.

경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

입력: 4

출력: 11

풀이

n이 홀수이면 타일을 전부 채울 수 없다.

• 직사각형 타일이 가로 크기가 짝수이기 때문에 가로, 세로가 전부 홀수인 바닥은 가득 채울 수 없다.

n=4일 때

• 이전 단계(n=2) 패턴(3가지)을 두 가지씩 조합하여 9가지 패턴을 만들 수 있다.
• 이전 단계에서 나오는 패턴을 조합하여 만들 수 없는 특수 패턴은 2가지이다.
• f(4) = 이전 단계 패턴 조합 + 현재 단계 특수 패턴
• = [2] 전체 패턴 × [2] 전체 패턴 +[4] 특수 패턴
• = f(2) × 3 + 2

n=6일 때

• 이전 단계에서 2칸이 추가되면서 특수 패턴도 2가지가 추가된다.
• 이전 단계 패턴 조합은 [4] 패턴이 왼쪽 × [2] 패턴이 오른쪽, [2] 패턴이 왼쪽 × [4] 패턴이 오른쪽으로 배치되는 두 유형이 있다.
• 다만 한 유형은 [2] 패턴 × [2] 패턴 × [2] 패턴으로 나올 수 있는 조합이 중복되므로 중복 제외 처리를 해야 한다.
• 중복되지 않는 패턴은 특수 패턴과 [2] 패턴이 조합되는 경우로, 앞선 조합이 [4] 전체 패턴 × [2] 전체 패턴이면 나머지 조합은 [2] 전체 패턴 × [4] 특수 패턴만 구하면 된다.
• f(6) = 이전 단계들 패턴 조합 + 현재 단계 특수 패턴
• = [4] 전체 패턴 × [2] 전체 패턴 + [2] 전체 패턴 × [4] 특수 패턴 + [6] 특수 패턴
• = f(n-2) × 3 + f(n-4) × 2 + 2

n=8일 때

• f(8) = [6] 전체 패턴 × [2] 전체 패턴 + [4] 전체 패턴 × [4] 특수 패턴 + [2] 전체 패턴 × [6] 특수 패턴 + [8] 특수 패턴
• = f(n-2) × 3 + f(n-4) × 2 + f(2) × 2 + 2

위에서 찾아낸 규칙으로 점화식을 만들 수 있다.

f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2

점화식을 간략화 해보면 다음과 같다.

f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2

// 피보나치 수열의 정의를 활용하여 변환
f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2
= 2(f(n-4) + ... + f(4) + f(2) + 1)
= f(n-2) - f(n-4)

f(n) = f(n-2)×3 + f(n-2) - f(n-4)
= f(n-2)×4 - f(n-4)

코드1. 점화식

• Kotlin

class Solution {
    fun solution(n: Int): Long {
        if (n % 2 != 0) return 0

        val dp = LongArray(n + 1)
        dp[0] = 1
        dp[2] = 3
        for (i in 4..n step 2) {
            dp[i] = dp[i - 2] * 3
            for (j in i - 4 downTo 0 step 2)
                dp[i] = dp[i] + dp[j] * 2
            dp[i] = dp[i] % 1000000007
        }
        return dp[n]
    }
}

• JAVA

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

• 정확성 테스트

테스트 1 〉	통과 (13.20ms, 74.7MB)
테스트 2 〉	통과 (20.08ms, 76.8MB)
테스트 3 〉	통과 (18.03ms, 78.7MB)
테스트 4 〉	통과 (17.37ms, 80.7MB)
테스트 5 〉	통과 (0.37ms, 73.2MB)
테스트 6 〉	통과 (8.23ms, 78.4MB)
테스트 7 〉	통과 (14.43ms, 73.3MB)
테스트 8 〉	통과 (19.67ms, 81MB)
테스트 9 〉	통과 (18.58ms, 77.7MB)
테스트 10 〉	통과 (4.27ms, 76MB)
테스트 11 〉	통과 (11.33ms, 78MB)
테스트 12 〉	통과 (4.38ms, 74.9MB)
테스트 13 〉	통과 (5.28ms, 76.3MB)
테스트 14 〉	통과 (4.93ms, 77MB)

• 효율성 테스트

테스트 1 〉	통과 (19.57ms, 51.7MB)
테스트 2 〉	통과 (18.70ms, 52.3MB)
테스트 3 〉	통과 (21.87ms, 52.4MB)
테스트 4 〉	통과 (19.71ms, 52MB)
테스트 5 〉	통과 (19.60ms, 52.3MB)
테스트 6 〉	통과 (20.36ms, 52.3MB)

코드 2. 점화식 간략화 + 나머지 연산 분배 법칙

• Kotlin

class Solution {
    fun solution1(n: Int): Long {
        if (n % 2 != 0) return 0

        val mod = 1000000007

        val dp = LongArray(n + 1)
        dp[0] = 1
        dp[2] = 3
        for (i in 4..n step 2) {
            dp[i] = (dp[i - 2] * 4 % mod - dp[i - 4] % mod + mod) % mod
        }
        return dp[n]
    }
}

• JAVA

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

• 정확성 테스트

테스트 1 〉	통과 (0.19ms, 78.3MB)
테스트 2 〉	통과 (0.24ms, 93.1MB)
테스트 3 〉	통과 (0.29ms, 86.2MB)
테스트 4 〉	통과 (0.29ms, 86.9MB)
테스트 5 〉	통과 (0.05ms, 75.7MB)
테스트 6 〉	통과 (0.17ms, 74MB)
테스트 7 〉	통과 (0.15ms, 73.6MB)
테스트 8 〉	통과 (0.26ms, 76.1MB)
테스트 9 〉	통과 (0.24ms, 73.4MB)
테스트 10 〉	통과 (0.18ms, 75MB)
테스트 11 〉	통과 (0.27ms, 67MB)
테스트 12 〉	통과 (0.18ms, 78.6MB)
테스트 13 〉	통과 (0.12ms, 70.5MB)
테스트 14 〉	통과 (0.17ms, 78.7MB)

• 효율성 테스트

테스트 1 〉	통과 (0.25ms, 52.6MB)
테스트 2 〉	통과 (0.25ms, 51.5MB)
테스트 3 〉	통과 (0.24ms, 52MB)
테스트 4 〉	통과 (0.24ms, 51.6MB)
테스트 5 〉	통과 (0.27ms, 52MB)
테스트 6 〉	통과 (0.25ms, 51.7MB)

[Kotlin] 프로그래머스 - 2 x n 타일링 - Dico

프로그래머스 코딩테스트 연습 타일링 풀이

dico.me