04/01 알고리즘 공부(82) - 멀리 뛰기

조건

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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. 우선 알고리즘을 짜기 위해서는 n과 result의 연관성을 찾을 필요가 있다.
   
   1. n -> result
      1 -> 1
      2 -> 2
      3 -> 3
      4 -> 5
      5 -> 8
      6 -> 13 .....
2. 놀랍게도 n과 result는 F(0) = F(1) = 1인 피보나치수열의 n번째 항의 값 result의 관계를 가지고 있다.
3. 따라서 이전 피보나치 수열의 n번째 수를 1234567로 나누었을 때의 알고리즘을 채용하되 F(0)를 0이 아닌 1로 바꾸어주어야 한다.

 

초기 코드

class Solution {
    fun solution(n: Int): Long {
        var answer: Long = 0
        return answer
    }
}

 

내 코드

class Solution {
    fun solution(n: Int): Int {
        val fibonacci = IntArray(n + 1) { 1 }
        for (i in 2..n) {
            fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % 1234567
        }
        return fibonacci[n]
    }
}

결과값은 항상 1234567보다 작기때문에 반환하는 자료형을 Int로 바꾸었다.

다른 사람의 풀이

class Solution {
    fun solution(n: Int): Long = getFibonacci(n + 1)
    private tailrec fun getFibonacci(currentNumber : Int, acc : Long = 0, prevSum : Long = 1) : Long =
        if(currentNumber == 0) acc
        else getFibonacci(currentNumber - 1, prevSum, (prevSum + acc) % 1234567)
}

 

개선점 또는 배운점

1. 처음에 관계성을 구하기 위해 5번항과 6번항의 값을 직접 구했지만 문제에서 주어진 조건을 반대로 생각해보면 쉽게 피보나치 관련 문제라는 것을 알 수 있다. 
   n번째 칸을 갈 수 있는 경우의 수는 n-1번째 칸에서 한 칸을 뛰거나 n-2번째 칸에서 두 칸 뛰는 방법밖에 없기 때문에 
   F(n) = F(n-1) + F(n-2)
   가 된다. 이는 피보나치수열의 점화식과 같다.
2. 위 풀이는 꼬리재귀함수를 이용해 n + 1번째의 피보나치수를 return한다. 다만 acc를 1로 바꾸었을 경우 F(0) = F(1) = 1일 때의 n번째항을 return할 수 있기 때문에 그 쪽이 좀 더 직관적라고 생각한다.