[프로그래머스 알고리즘] 피보나치 수 (level 2)

문제

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

과정1 (재귀)

피보나치 수는 F(n) = F(n-1) + F(n-2) 가 적용되는 수로, 식과 같이 재귀로 풀 수 있다.
따라서, 처음에 재귀로 풀되, 메모이제이션을 적용하여 중복되는 과정을 없애고 코드를 짰다.

import java.util.*;
//
class Solution {
//    
    public static int[] fibArr = new int[100001];
//    
    public static int fib(int n){
        if(fibArr[n] != 0){			//이미 구한 수이면 바로 리턴 
            return fibArr[n];
        }
        if(n == 0 || n == 1) {
            return n;
        }
//
        fibArr[n] = fib(n - 1) + fib(n - 2);	//메모이제이션
        return fibArr[n];
//
    }
//    
    public int solution(int n) {
        int answer = 0;
        int fibNum = fib(n);
        answer = fibNum % 1234567;
//        
        return answer;
    }

그런데, 시간초과가 났음.

과정2 (반복문)

재귀는 함수 호출이기 때문에 속도가 느리다. 따라서 반복문으로 풀어보았다.

import java.util.*;
//
class Solution {
//    
	 public int solution(int n) {
        int answer = 0;
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2; i <= n; i++){
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        answer = fib[n];
//        
        return answer;
    }
}

처음에는 1234567로 나누어 나머지는 구하는 과정을 마지막만 했는데, 정답이 아니었다.
최대 수가 20만이기 때문에 20만번째 피보나치 수를 구하면 오버플로우가 나기 때문이었다.
따라서, 피보나치 수를 구할 때마다 1234567로 나눈 나머지를 저장하였다.
분배법칙이 있기 때문에 이것이 가능하다.
(1 + 2 + 3 + 4) % 10 = 1 + 2 + 3 + 4
1 % 10 + 2 % 10 + 3 % 10 + 4 % 10 = 1 + 2 + 3 + 4