[Kotlin] Korean Coding Test - Programmers - 3 x n Tiling
KotlinQuestion
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.
text
f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2The ignition equation is simplified as follows.
text
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
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
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
text
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
text
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
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
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
text
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
text
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)
