백준 알고리즘 10870번 피보나치 수열 JAVA

 

 

백준 알고리즘 10870번은 피보나치 수를 구하는 알고리즘이다. 시작은 0과1로 시작하며 2 이상의 자연수 N이 주어졌을 때 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 순서로 진행된다. 

 

 

피보나치 수열의 공식은 Fn = Fn-1 + Fn-2 (n ≥ 2)이다. 뒤의 2개의 수의 합이 현재의 수를 결정하게 되는 것이다. 유럽에서 최초로 피보나치 수를 연구한 건 레오나르도 다빈치라고 한다. 토끼의 수가 늘어나는 원리로 설명했었는데, 태어난지 얼마 안된 토끼가 새로운 토끼를 낳을 수는 없기 때문이다.

 

풀이

백준 알고리즘 10870번 풀이 방법은 재귀함수를 사용하는 것이다. 재귀함수를 사용하기 위해서는 초기 셋팅값을 던져주고, 탈출 조건을 명시해줘야 한다. 이번 문제에서 탈출조건을 맞추기 위해서 count 변수를 사용했다. 피보나치 수를 담기 위한 int형 배열을 만들어서 재귀함수를 호출한다.

 

 

 

JAVA 코드

import java.util.Scanner;

// 피보나치 수열 구하기
public class Main {
    public static int[] arr;
    public static int count=0;
    public static void main(String[] args){
    	// 입력값을 받는다.
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        
        // 입력받은 값으로 배열을 생성한다.
        arr = new int[N+2];
        arr[0] = 0;
        arr[1] = 1;
        
        // 재귀 함수 시작
        fibonazzi(0,1);
        
        System.out.println(arr[N]);
    }

    public static int fibonazzi(int N_1, int N_2){
    	// 탈출조건
        // count는 0부터 시작하며 전체 배열길이는 N+2다.
        if(count+2==arr.length){
            return 0;
        }
        
        // 피보나치 공식 [Fn = Fn-1 + Fn-2 (n ≥ 2)]
        int N_3 = N_1+N_2;
        arr[count+2]=N_3;
        count++;
        return fibonazzi(N_2, N_3);
    }
}