[백준] 10870번 – 피보나치 수 5(JAVA)

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

- 문제 -

---

- 풀이 과정 -

피보나치 수는 문제에 있듯이 0과 1로 시작하며 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 됩니다.

 

예를 들어

[세번째 피보나치 수 = 첫번째 + 두번째 피보나치 수]

[다섯 번째 피보나치 수 = 세 번째 + 네 번째 피보나치 수]가 되기에

 

Fn = Fn-1 + Fn-2 (n ≥ 2)의 공식이 성립하게 됩니다.

 

그렇기에 N번째 피보나치 수를 구하기 위해서 N-1, N-2 번째 피보나치 수를 알아야 합니다.

또한 N-1, N-2번째 피보나치 수가 0 또는 1이 아닌 경우 N-1, N-2번째의 이전 피보나치 수를 알아야 합니다.

N-1 -> (N-1)-1 , (N-1)-2

N-2 -> (N-2)-1 , (N-2)-2 

 

이런 식으로 현재 차례(N)에서 N-1, N-2의 차례 값을 재귀 함수로 호출하며 N의 값이 0 또는 1이 나올 때까지 수행합니다.

재귀 호출을 수행해서 내려가다 보면 N의 값이 0 또는 1이 나오는데 이때 반환 값을 0,1로 반환합니다.

반환된 값으로 피보나치 수의 합을 시작하면서 돌아오면 N번째 피보나치 수의 합을 구할 수 있습니다.

---

- 소스 코드 -

package com.test;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    //10870번 - 피보나치 수 5
    public static void main(String[] args) throws IOException{
        //0 1 1 2 3 5 8 13 21
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int i=Integer.parseInt(br.readLine());
        
        int fibo=fibonacci(i);
        System.out.println(fibo);
        
    }
    public static int fibonacci(int i) {
        if(i==1) return 1;
        if(i==0) return 0;
        
        return fibonacci(i-1)+fibonacci(i-2);
    }
}