프로그래머스 lv2 피보나치 수

문제 링크

피보나치 수

풀이

• 처음에는 간단하게 재귀로 풀 수 있는줄 알고 재귀로 풀었다.
• 근데 시간 초과 발생하네...?
• 뭐가 문젠지 공부좀 해봤고, 해당 문제는 재귀가 아닌 dp로 풀어야한다는 것을 깨달았다.
• dynamic programming으로 코드를 작성했으나..그러나 이번엔 결과 값이 다르게 나왔다.
• 뭐가 문제인가 해서 디버깅해보니, 피보나치 수의 값이 int 값의 범위를 넘어서면서 오버플로우가 발생하던 것이었다.
• 문제를 다시 읽어보니, 피보나치 수를 1234567로 나눈 값을 리턴하라고 했었고 이 조건을 이용해서 모듈러 연산법칙을 이용한 코드를 작성했다.
• (a+b) % M = ((a % M) + (b % M)) % M

class Solution {
    public int solution(int n) {
       return fibonacci(n);
    }

    public int fibonacci(int n) {
        int[] memory = new int[n + 1];
        memory[0] = 0;
        memory[1] = 1;

        for (int i = 2; i <= n; i++) {
            memory[i] = (memory[i - 1] + memory[i - 2]) % 1234567;
        }

        return memory[n];
    }
    
// recursive - time over.
//    public static int fibonacci(int n) {
//        if (n == 0) return 0;
//        if (n == 1) return 1;
//        return fibonacci(n - 1) + fibonacci(n - 2);
//    }
}

• 모듈러 연산...을 어떻게 갑자기 생각해내는거지 사람들 신기하네