[프로그래머스] Lv.2 피보나치 수 (java)

2023.04.27 Complete !

🔈 문제 설명

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

📝 입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

💛 내가 쓴 풀이

import java.util.*;
class Solution {
    
	public static int[] arr;
    public int solution(int n) {
        int answer = 0;
		arr = new int[n+1];
		answer = fibo(n);
        return answer;
    }
    
	public static int fibo(int n) {
		if (n < 2)
			return n; 
		else if (arr[n] != 0) 	
			return arr[n];
		else 
            return arr[n] =  (fibo(n-2) + fibo(n-1))%1234567;
	}
}

재귀 함수의 경우 호출 횟수를 고려해야한다.
제한 사항을 보면 n은 2 이상 100,000 이하인 자연수입니다. 라는 조건이 있다.

한 함수에서 두 개의 함수를 호출하여 호출이 2배씩 늘어나기 때문에 시간 복잡도가 O(2^N) 라고 한다. 메모이제이션을 사용하면 해결가능하다고 한다.

❗ 시간 초과 났던 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
		answer = fibo(n)%1234567;
        
        return answer;
    }
    public int fibo(int n) {
		if (n <= 1)
			return n;
		else 
            return fibo(n-2) + fibo(n-1);
	}
}