[Kotlin] Korean Coding Test - Programmers - 2 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 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

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

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

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

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)

[Kotlin] Korean Coding Test - Programmers - Fibonacci Number - Dico

프로그래머스 코딩테스트연습 피보나치수 kotlin 풀이

dico.me