피보나치 수 | 프로그래머스

김태영·2024년 6월 10일

코딩 테스트

목록 보기

15/33

📍 피보나치 수

💡 문제

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

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

⚠️ 제한사항

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

✅ 풀이

👆 첫 번째 풀이 (실패)

재귀 함수를 이용해 n번째 피보나치 수를 구하고, 1234567로 나눈 나머지를 반환하는 방식으로 풀이했다. n에서 2를 빼준 이유는, 0번째와 1번째 피보나치 수를 인자로 넣어주었기 때문에 재귀 함수가 반환하는 피보나치 수는 3번째 수부터 시작되기 때문이다.

그러나, 이 풀이는 실패했다. 제한사항에서 n은 최대 100,000이고 피보나치 수의 특성상 n이 커지면 커질수록 크기가 기하급수적으로 커진다. Int 범위를 넘어갔을 때부터는 연산의 정확성이 보장되지 않기 때문에 답을 정확히 맞추지 못하는 것이다. 자료형을 Long으로도 바꿔서 풀어봤지만, 정답률은 여전히 50%를 넘지 못했다. Long의 범위도 넘어가는 것이다..

class Solution {
    tailrec fun fibo(x: Int, y: Int, cnt: Int): Int {
        return if (cnt == 0) x + y else fibo(y, x + y, cnt - 1)
    }
    
    fun solution(n: Int): Int {
        return fibo(0, 1, n - 2) % 1234567
    }
}

✌️ 두 번째 풀이 (성공)

어차피 나머지를 구해야 되는 거면, 아예 처음부터 1234567로 나눈 나머지를 사용해 피보나치 수를 구하는 방법이 있겠다. 코드가 반복되는 감이 없지 않아 있지만, 풀이에는 성공했다.

class Solution {
    tailrec fun fibo(x: Int, y: Int, cnt: Int): Int {
        return if (cnt == 0) (x + y) % 1234567 else fibo(y % 1234567, (x + y) % 1234567, cnt - 1)
    }
    
    fun solution(n: Int): Int {
        return fibo(0, 1, n - 2)
    }
}

🔥 다른 사람의 풀이

재귀함수 대신 반복문을 사용해 풀이했다. 역시 반복문을 사용하는 게 가독성이 더 좋은 것 같다. 나머지 연산을 3번이나 쓴 내 풀이보다는 훨씬 나은 풀이같다.

class Solution {
    fun solution(n: Int): Int {
        var ans = Array(n+1) { i -> 0 }
        ans[1] = 1
        for(i in 2..n) ans[i] = (ans[i-1] + ans[i-2])%1234567
        return ans[n]
    }
}