[프로그래머스/Kotlin] 피보나치 수

문제 링크->https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

피보나치 수는 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 이하인 자연수입니다.

------------------------------------------------------------풀이------------------------------------------------------------------
먼저 저의 풀이입니다. 
- 피보나치수열은 f(n)= f(n-1) + f(n-2)입니다. 

class Solution {
    fun solution(n: Int): Int = search(arrayListOf<Int>(0, 1), n, 2)
    

    fun search( f : ArrayList<Int>, target : Int, now : Int) : Int = if( now != target) {
        f.add((f[now-2]%1234567+f[now-1]%1234567)%1234567)
        search(f, target, now+1)
    }
    else{
        f.add((f[now-2]%1234567+f[now-1]%1234567)%1234567)
        f.last()
    }
}

1. 0과 1은 고정시켜놓고 target 과 현재 index를 입력받아 재귀함수로 구현합니다. 

풀이를 보시면 각 index의 value값에 1234567을 나누어서 나머지를 저장합니다. 이부분은 뒤에서 말씀드릴겠습니다.

첫 번재로 불통한 코드 

class Solution {
    fun solution(n: Int): Int {
        var f = arrayListOf<Int>(0, 1)

        for( i in 2..n){
            f.add(f[i-2]+f[i-1])
        }

        return f.last()%1234567
    }
}

처음에 에이 쉽네 하고 풀었다가 뒤통수 시게맞은 코드입니다. 7번부터 전부 에러더군여. 
왤까 하고 생각하다가 value값 크기에 대해 생각했습니다. int형은 4바이트로 표현값이 
-2,147,483,648 ~ 2,147,483,647입니다. 
근데 피보나치 수열을 쭉 그냥 뽑아봤는데 

 

47번째부터 -값이 나옵니다. 2,147,483,647을 넘는 순간 -2,147,483,648부터 시작하기 때문이었습니다.. 자료형의 데이터 범위를 생각하지 않아서 그런것이었습니다. 

그럼 어떻게 하냐

 

위 문제에서 1234567로 나눈 나머지를 return하라고 되어있습니다. 
학교에서 언뜻 배운게 생각나서 
f(n) = f(n-2) + f(n-1) 이니까
f(n)%1234567 = f(n-2)%1234567 + f(n-1)1234567 이었던거 같은데 하고 해보니 틀렸습니다... 값을 뽑아보니 
f(n)%1234567 = ( f(n-2)%1234567 + f(n-1)1234567 )%1234567 이렇게 마지막에 한번 더 해줘야 하더라구여 
그래서 맨위에 코드가 탄생했습니다! 
* 원래는 불통한 코드처럼 람다를 사용하지 않았는데 람다식에 익숙해질겸 해서 람다로 변경한 코드입니다.

위에 사용된 식이 모듈러 정리라고 하는데 궁금하신분들은 구글에 검색하시면 엘리트 개발자 분들이 블로그에 많이 정리해놓으셨습니다 ㅎㅎ 
------------------------------------------------------------결과------------------------------------------------------------------

- 문제에 대한 질문 댓글 환영!
- 중간에 잘못된 부분이 있다면 댓글로 남겨주세요. 수정하겠습니다.