피보나치 수

문제 : 

출처 : https://programmers.co.kr/learn/courses/30/lessons/12945

 

이 문제는 일반 지문 설명이 많이 부족했다. 단순히 n번째의 피보나치 수를 1234567로 나눈 나머지를 구하는 문제인줄 알았는데 코드 제출하니 7번부터 계속 타임아웃나서 다른 사람의 풀이를 보고 문제의 해답을 찾았다.

 

 > 각 피보나치 수를 1234567로 나눈 나머지의 값들을 다 더하는 거였다.

 

예) 

   f(0) = 0, f(1) = 1,

   f(2) = f(1) %1234567 + f(0) % 1234567 = 1 + 0 = 1

   f(3) = f(2) % 1234567 + f(1) % 1234567 = 1 + 1 = 2

 

다시 구한 나의 정답

class Solution {
    public int solution(int n) {	
        if(n == 2){
            return 2;
        }
        
        int[] fibo = new int[n+1];
        fibo[0] = 0;
        fibo[1] = 1;
        
        for(int i=2; i<=n; i++){
             fibo[i]= ( (fibo[i-2] + fibo[i-1]) % 1234567);
        }    
        return fibo[n];
    }  
   /*
    public static int fibo(int number){
        
        if(number == 0){
            return 0;
        }else if(number == 1){
            return 1;
        }else { 
            return fibo(number-2) + fibo(number-1);
        }   
    }
    */
}