[Kotlin] Korean Coding Test - Programmers - 2 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 length 2 and length n. There are two ways to fill a tile.
- When placing tiles horizontally
- When placing tiles vertically
For example, a rectangle with n 7 can be filled as follows.
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 60,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: 5
Solve
Find a Rule
- The nth value from the time n=3 is the result of adding the n-1th value and the n-2th value.
- It is a matter of finding the Fibonacci sequence.
- It uses a dynamic programming (DP) bottom-up method.
Code. Kotlin
kotlin
class Solution {
fun solution(n: Int): Int {
val answer = IntArray(n + 1)
answer[1] = 1
answer[2] = 2
for (i in 3..n)
answer[i] = (answer[i - 1] + answer[i - 2]) % 1000000007
return answer[n]
}
}Code. JAVA
java
class Solution {
public int solution(int n) {
int[] answer = new int[n+1];
answer[1] = 1;
answer[2] = 2;
for (int i=3; i<=n; i++) {
answer[i] = (answer[i - 1] + answer[i - 2]) % 1000000007;
}
return answer[n];
}
}- Accuracy test
text
TEST 1 〉 Pass (0.37ms, 67.8MB)
TEST 2 〉 Pass (0.08ms, 68.3MB)
TEST 3 〉 Pass (0.15ms, 75.4MB)
TEST 4 〉 Pass (0.40ms, 66.8MB)
TEST 5 〉 Pass (0.09ms, 79.7MB)
TEST 6 〉 Pass (0.33ms, 74.6MB)
TEST 7 〉 Pass (0.05ms, 77.4MB)
TEST 8 〉 Pass (0.18ms, 74.9MB)
TEST 9 〉 Pass (0.16ms, 71.6MB)
TEST 10 〉 Pass (0.44ms, 77.6MB)
TEST 11 〉 Pass (0.22ms, 76.8MB)
TEST 12 〉 Pass (0.05ms, 75.8MB)
TEST 13 〉 Pass (0.07ms, 71.4MB)
TEST 14 〉 Pass (0.21ms, 67.6MB)- Efficiency test
text
TEST 1 〉 Pass (0.93ms, 52.5MB)
TEST 2 〉 Pass (1.38ms, 52.2MB)
TEST 3 〉 Pass (0.97ms, 52.4MB)
TEST 4 〉 Pass (0.68ms, 52.5MB)
TEST 5 〉 Pass (1.47ms, 52.1MB)
TEST 6 〉 Pass (2.30ms, 64.4MB)
