[프로그래머스] 멀리 뛰기 with Kotlin

문제

한 번에 1칸 또는 2칸 뛸 수 있으며, 칸이 N으로 주어졌을 때 N까지 뛸 수 있는 모든 경우의 수의 개수를 반환하는 문제

 

풀이 과정

1칸 : 1

2칸 : 2

3칸 : 3

4칸 : 5

5칸 : 8

 

다음과 같은 규칙으로 증가하는 피보나치 수이므로 다이나믹 프로그래밍을 사용하여 해결할 수 있다.

 

코드

class Solution {
    fun solution(n: Int): Long {
        if(n == 1) return 1
        
        val dp = Array(n){0}
        dp[0] = 1
        dp[1] = 2
        
        for(i in 2 until n){
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567
        }
        
        return dp[n-1].toLong()
    }
}