8월 11일 99클럽 항해 21일

99클럽 항해 21일차

 

오늘의 문제는 피보나치 수이다.

 

 

피보나치 수열을 구현하고 해당 값에서 1234567을 나누는 문제이다.

    -> 재귀함수를 이용하여 피보나치 수열을 구현하고 해당 수를 1234567로 나눈 나머지를 구한다.

순으로 문제를 해결하였다. 하지만,

class Solution {
    public int solution(int n) {

        int answer = fibonacci(n)%1234567;
        return answer;
    }
    public int fibonacci(int count){
        if(count<=1){
            return count;
        }
        else{
            return (fibonacci(count - 1) + fibonacci(count - 2));
        }
        }
    }

 

재귀함수를 이용한 피보나치 수열 구현은 수가 커지면 소요 시간이 커져 테스트 케이스에서 오류가 발생하게 되었고, 이에따라 방법을 바꾸어 동적 계획법(Dynamic Programming)을 사용하였다.

 

class Solution {
    public int solution(int n) {
        int[] answer = new int[n+1];
        answer[0] = 0;
        answer[1] = 1;
        
        for(int i=2; i<=n; i++){
            answer[i] = (answer[i-1]+answer[i-2])%1234567;
        }
        
        return answer[n]%1234567;
    }
}