[Programmers] 멀리뛰기 (Kotlin)

[멀리 뛰기]

Programmers 멀리 뛰기

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한사항

• n은 1 이상, 2000 이하인 정수입니다.
  
  

입출력 예

n	result
4	5
3	3

입출력 예 설명

입출력 예 #1

위에서 설명한 내용과 같습니다.

입출력 예 #2

(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

풀이

규칙을 찾기 위해서 1부터 5까지 직접 구해보았다.

n	result
1	1
2	2
3	3
4	5
5	8

중고등학생 때 배웠던 피보나치 수열이다.
피보나치 수의 점화식은 아래와 같다.

$F_0 = 0$
$F_1 = 1$

$n ∈ \{ 2,3,4, ... \}$
$F_n = F_{n-1} + F_{n-2}$

이것을 활용하여 코드를 작성하면 된다!

코드

class Solution {
	fun solution(n: Int): Long {
    	if (n == 1) return 1
        
        var (prev, current) = 1L to 1L
        
        for (i in 2..n) {
        	val temp = current
            current = (prev + current) % 1234567
            prev = temp
        }
    }
}