[Kotlin] Korean Coding Test - Programmers - 3 x n Tiling

Question

Link

There are rectangular tiles with a length of 2 and a length of 1. Using this rectangular tile, you want to fill a floor with 3 vertical and n horizontal. There are two ways to fill a tile.

• When placing tiles horizontally
• When placing tiles vertically

When the horizontal length n of the rectangle is given as a parameter, complete the solution function that returns the number of ways to fill this rectangle.

Restrictions

The length n of the horizontal is a natural number of less than 5,000.

The number of cases may increase, so please return the rest after dividing the number of cases by 1,000,000,007

Input/Output example

Input: 4

Output: 11

Solve

If n is odd, you cannot fill up all the tiles.

• Because rectangular tiles are even in horizontal size, floors that are both odd in width and length cannot be filled.

When n=4

• Nine patterns can be created by combining two patterns of the previous step (n=2).
• There are two special patterns that cannot be created by combining the patterns from the previous step.
• f(4) = Combination of previous stage patterns + current stage special pattern
• = [2] Full pattern × [2] Full pattern +[4] Special pattern
• = f(2) × 3 + 2

When n=6

• As two spaces were added in the previous step, two special patterns were also added.
• There are two types of previous pattern combinations in which the pattern [4] is placed left × [2] is placed to the right, and the pattern [2] is placed to the left × [4] is placed to the right.
• However, since one type overlaps a combination that can appear as a [2] pattern × [2] pattern × [2], duplicate exclusion processing must be performed.
• The non-overlapping pattern is a combination of a special pattern and a [2] pattern, and if the previous combination is [4] overall pattern × [2] overall pattern, the remaining combination only needs to obtain [2] overall pattern × [4] special pattern.
• f(6) = Combination of previous steps pattern + current stage special pattern
• = [4] Full pattern × [2] Full pattern + [2] Full pattern × [4] Special pattern + [6] Special pattern
• = f(n-2) × 3 + f(n-4) × 2 + 2

n=8일 때

• f(8) = [6] Full pattern × [2] Full pattern + [4] Full pattern × [4] Special pattern + [2] Full pattern × [6] Special pattern + [8] Special pattern
• = f(n-2) × 3 + f(n-4) × 2 + f(2) × 2 + 2

You can create an ignition equation with the rules found above.

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

The ignition equation is simplified as follows.

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

// Transform using definition of Fibonacci sequence
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)

Code 1. Ignition Type

• 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];
    }
}

• Accuracy test

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

• Efficiency test

TEST 1 〉	Pass (19.57ms, 51.7MB)
TEST 2 〉	Pass (18.70ms, 52.3MB)
TEST 3 〉	Pass (21.87ms, 52.4MB)
TEST 4 〉	Pass (19.71ms, 52MB)
TEST 5 〉	Pass (19.60ms, 52.3MB)
TEST 6 〉	Pass (20.36ms, 52.3MB)

Code 2. Ignition Simplification + Remaining Calculation Distribution Law

• 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];
    }
}

• Accuracy test

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

• Efficiency test

TEST 1 〉	Pass (0.25ms, 52.6MB)
TEST 2 〉	Pass (0.25ms, 51.5MB)
TEST 3 〉	Pass (0.24ms, 52MB)
TEST 4 〉	Pass (0.24ms, 51.6MB)
TEST 5 〉	Pass (0.27ms, 52MB)
TEST 6 〉	Pass (0.25ms, 51.7MB)

[Kotlin] Korean Coding Test - Programmers - 2 x n Tiling - Dico

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

dico.me