프로그래머스 피보나치 수 Kotlin (dp)

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

풀이

피보나치에 관한 간단한 문제이다.

아래 두 개의 코드가 있다.

첫 번째 코드는 그냥 반복문을 이용해 사이즈3 배열에 마지막 칸에 계산한 값을 넣고, 한 칸씩 땡기고, 다시 계산하고

이를 반복하는 코드다.

두 번째 코드는 재귀 + 메모이제이션을 이용했는데, 피보나치 재귀는 워낙 웰논이니 딱히 설명하진 않겠다. 코드 보면 바로 이해갈 것이다.

다만, 피보나치 재귀는 메모이제이션 없이 돌리면 O(2^n)의 시간복잡도이다. 메모이제이션으로 중복 탐색을 줄이면 O(n)의 시간복잡도로 풀 수 있다.

 

코드1(반복문)

class Solution {
    fun solution(n: Int): Int {
        var arr = arrayOf(1,1,1)
        if(n==2) return 1
        repeat(n-2){
            arr[2] = (arr[0]+arr[1])%1234567
            arr[0] = arr[1]
            arr[1] = arr[2]
        }
        return arr[2]
    }
}

코드2(재귀 + 메모이제이션)

class Solution {
    lateinit var arr: IntArray
    fun solution(n: Int): Int {
        arr = IntArray(n+1)
        arr[1] = 1
        return fibonacci(n)
    }
    tailrec fun fibonacci(n: Int): Int{
        if(n<2) return arr[n]
        if(arr[n]>0) return arr[n]
        return  ((fibonacci(n-1)+ fibonacci(n-2))%1234567).also { arr[n] = it }
    }
}