피보나치 수

문제 설명

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

입출력 예

n	return
3	2
5	5

입출력 예 설명

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

실패한 코드 => 시간초과

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        answer = recur(n)%1234567;
        
        return answer;
    }
    
    public int recur(int num){
        if(num == 0) return 0;
        else if(num == 1) return 1;
        else{
            return recur(num-1)+recur(num-2);
        }
    }
}

피보나치를 재귀의 방법으로 풀면 결과값에 문제는 없지만 시간 초과가 나오는 문제가 생기다!!!!

반복문을 사용해서 문제를 해결하면 된다!

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        answer = recur(n);
        
        return answer;
    }
    
    public int recur(int num){
        int a=1, b=1;
        int result = 0;
        if(num==2 || num==3)
            result = 1;
        for(int i=3; i<=num; i++){
            result = a+b;
            a = b % 1234567;
            b = result % 1234567;
        }
        
        return result % 1234567;
    }
}

반복문을 사용해서 해결한 문제이지만 ----> 왜 다음 계산으로 넘어갈 때 %1234567을 각각 해주는 걸까??

이 문제에 대해서는 질문하기 항목에서 답을 찾을 수 있었다.

https://programmers.co.kr/questions/11991 ( 좋은글 너무나도 감사합니다!)

프로그래밍 시, 정수의 범위는 아주 중요한 부분이다.

int라는 자료형은 -2,147,483,648 ~ 2,147,483,647 까지의 값만을 표현할 수가 있는데,

만약 2,147,483,647이라는 값을 가지고 있는 int형 숫자에 1을 더하게 되면 2,147,483,648이 나오는게 아니라 -2,147,483,648이 나오게 된다 === 이것의 의미는 각 자료형의 범위가 넘어가게되면 예상하지 못한 결과가 나오게 된다는 의미이다!!!

다시 문제 이야기로 돌아가면 피보나치의 수는 커지는 속도가 아주 빠르다. 44번째만 되도 int의 범위를 넘어버린다고 한다. 여태까지의 설명을 빗대어보면 대충 int값을 넘어가면 예상하지 못한 결과가 나온다는 의미이다.

여기서 사용한 성질이 있다

( A + B ) % C = ( ( A % C) + ( B % C ) ) % C

이러한 과정이기 때문에 문제에서 다음 피보나치 계산으로 넘어가기 전에 처리를 해준 부분이다.

즉 문제에서 어려우라고 껴둔게 아니라 int의 범위 내에 항상 값이 있도록 보장해주는 부분이다!!

****