문제

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

도전 1

public class Fibonacci {
    public static void main(String[] args) {
        int su = 3;
        Fibonacci fibo = new Fibonacci();
        int solution = fibo.solution(su);
        System.out.println("solution = " + solution);
    }

    public int solution(int n) {
        if(n<0) return 0;
        //n이 1보다 작거나 같으면 그 값을 그대로 return 0,1
        if(n<=1) return n;
        //그 외 값들은 트리 구조로 계속 호출
        return solution(n-1)+ solution(n-2);
    }
}

피보나치는 전형적인 dfs문제 아니였나... 하는 생각에 너무 쉽지 하며 다음과 같이 풀었다. 하지만 바로

다음과 같이 테스트에서 터져버린다. 그 이유는 해당 문제를 재귀로 풀었을 때 재귀의 단점 때문에 풀어낼 수 없는 것인데.

재귀로 풀었을 때 장점
1. 코드가 깔끔해진다.

재귀로 풀었을 때 단점
1. 메모리 사용량이 커진다. (call stack 사용량)
2. 성능이 느리다.

라는 문제점을 알려주는 문제였나보다... 그래서 다음으로 dynamic programing으로 fibonacci를 푸는 방법을 생각해봤다.

도전2

public class Fibonacci {
    public static void main(String[] args) {
        int su = 7;
        Fibonacci fibo = new Fibonacci();
        int solution = fibo.solution(su);
        System.out.println("solution = " + solution);
    }

    static int[] dy;
    public int solution(int n) {
        dy = new int[n+1];
        return dynamic(n);
    }
    public int dynamic(int n){
        dy[0] = 0;
        dy[1] = 1;
        if(n<0) return dy[0];
        for(int i=2; i<=n; i++){
            dy[i] = dy[i-2] + dy[i-1];
        }
        return dy[n];
    }
}

이번에는 자신이 있었다... 하지만

성능 자체는 많이 개선된거 같은데... 실패가 뜬다... 그래서 질문하기 탭을 클릭하여 보니...! 테스트 케이스 7번부터는 1234567보다 큰 값을 넣어서 실패가 뜨는거였다... 지문 좀 제대로 읽자 ㅜㅜ

정답

public class Fibonacci {
    public static void main(String[] args) {
        int su = 7;
        Fibonacci fibo = new Fibonacci();
        int solution = fibo.solution(su);
        System.out.println("solution = " + solution);
    }

    static int[] dy;
    public int solution(int n) {
        dy = new int[n+1];
        return dynamic(n);
    }
    public int dynamic(int n){
        dy[0] = 0;
        dy[1] = 1;
        if(n<0) return dy[0];
        for(int i=2; i<=n; i++){
            dy[i] = ((dy[i-2]%1234567) + (dy[i-1]%1234567))%1234567;
        }
        return dy[n];
    }
}

결국 정답을 맞췄다... 모듈러 연산이라고 하는 개념을 대학교 때 보고 본적이 없었는데... 교수님께 죄송하다...ㅜㅜ

dy[i] = ((dy[i-2]%1234567) + (dy[i-1]%1234567))%1234567;

해당 부분의 연산식이 중요했는데. 그 이유는 dy[i]에 %1234567의 값을 넣기 위해서는

(A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C

의 연산 공식을 알고 있었어야했기 때문이다!