[프로그래머스] 피보나치 수 - Java

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

코딩테스트 연습 - 피보나치 수

---

문제

문제 설명

피보나치 수는 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, ... 와 같이 이어집니다.

---

풀이

풀이 과정

피보나치 수를 구하는 알고리즘을 재귀함수를 이용해서 구하면 구하고자 하는 수가 커질수록 중복계산이 많이 발생해 효율성이 떨어지게 된다

따라서 이전에 구한 결과값을 저장 해놓고 필요한 경우 사용하는 동적계획법을 이용한다

구하고자 하는 피보나치 수의 최대값이 100,000이므로 0을 100,001 크기만큼의 배열을 생성해두고 값을 저장하는데 이용한다

class Solution {
    static int[] data = new int[100001];
}

 

 

- 피보나치 수를 구하는 함수 작성

피보나치 수 0과 1의 값은 그대로 0과 1이므로 n이 2보다 작은경우에는 바로 n값을 return

만약 data 배열에 이전에 구한 n값이 있다면 해당 값을 1234567로 나눈 값을 return

처음으로 구하는 값이라면 값을 return하는 동시에 data 배열에 저장

private static int fibonacci(int n) {
    if(n < 2) return n; // 0과 1은 그대로 return
    if(data[n] != 0) return data[n] % 1234567; // n번째 피보나치 수 / 1234567 값 return

    return data[n] = (fibonacci(n - 1) + fibonacci(n - 2)) % 1234567;
}

 

최종 코드

class Solution {
    static int[] data = new int[100001]; // 최대값 100000
    
    public int solution(int n) {
        int answer = 0;
        
        answer = fibonacci(n);
        
        return answer;
    }
    
    private static int fibonacci(int n) {
        if(n < 2) return n; // 0과 1은 그대로 return
        if(data[n] != 0) return data[n] % 1234567; // n번째 피보나치 수 / 1234567 값 return
		
        return data[n] = (fibonacci(n - 1) + fibonacci(n - 2)) % 1234567;
    }
}

---