(알고리즘) 멀리 뛰기 풀이

프로그래머스 멀리뛰기 문제를 풀면서 어떤 방식으로 접근해야 할 지 고민을 좀 했다

 

해당 문제는 멀리뛰기를 1칸 또는 2칸을 할 수 있고 해당 방법으로 맨 끝 칸 까지 갈 수 있는 경우의 수를 구하는 문제이다

 

사실 여러가지 방법이 있지만 나는 그림을 그려 보았다 

사실 1과 2일 경우에는 1 하나와 (1,1) , 2 이렇게 2개 가 있어서 1과 2가 나올 것이고 3부터 그림을 그려서 얼추 가짓수를 생각해보았다

그런데 이 갯수가 1 -> 2 -> 3 -> 5 -> 8 ... 이렇게 커지는 것이 아닌가?? 사실 이건 어디서 많이 본 것 같은데.. 바로 피보나치의 수열을 생각해보았다

 

피보나치의 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이라고 한다

 

이번 문제에서는 0이 존재하지 않으므로 0의 항이 1인 것을 생각 하면 피보나치의 수열로 푸는 것이 가능할 것이라고 생각 했다

 

그러면 어떤 식으로 접근 할 것인가

 

우선 문제에는 최대 2000 의 정수라고 한다 그말은 1번씩 뛰어서 총 2000번 갈 수 있다는 뜻이다 그리고 1 경우의 수는 1이고 2의 경우의 수는 2이므로 2를 넣어준다

 

그러면 지금까지 코드는 이렇게 된다

fun solution(n: Int): Long {

    var arr = IntArray(2000)

    arr[1] = 1
    arr[2] = 2
    for(i in 3 until arr.size){

       TODO()
    }

 

여기서 3부터는 피보나치의 수열을 이용하려고 하는데 피보나치의 수열은 첫째 항과 둘째 항의 합 즉 

(arr[i - 1] + arr[i - 2])

 

이 값이 된다 여기서 문제에는 1234567을 나눈 나머지를 리턴해달라고 했으니까 아래와 같이 코드를 구성하면 될 것 같다

(arr[i - 1] + arr[i - 2]) % 1234567

 

따라서 위의 코드와 아래의 코드를 종합해보면 이렇게 된다

 

fun solution(n: Int): Long {

    var arr = IntArray(2000)

    arr[1] = 1
    arr[2] = 2
    for(i in 3 until arr.size){

        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567
    }



    return arr[n].toLong()
}

 

이상이다