[백준] - 피보나치 수 5 (10870) (자바/Java)

 

 

 

 

 

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

 

 

 

 

 

문제.

---

 

 

 

 

 

 

 

 

풀이.

---

 

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();

        System.out.println(Fibonacci(a));

    }

    static int Fibonacci(int a) {
        if (a == 0) {
            return 0;
        }
        if (a == 1) {
            return 1;
        }
        return Fibonacci(a - 1) + Fibonacci(a - 2);
    }
}

 

이번 문제에서는 재귀함수를 사용했다.

우선 문제를 풀기 전에 "피보나치 수"를 이해해야 한다.

 

피보나치 수 란?

첫번째 항이 0부터 시작할 경우 첫 번째 항은 0, 두 번째 항은 1부터 시작하여, 다음 항은 직전 항과 직전 항의 합으로 이루어진 수열을 의미한다.

 

예를 들자면 N = 5 일경우

0, 1, 1, 2, 3, 5 인것이다.

 

그럼 본론으로 돌아와 피보나치 수는 첫 번째 항과, 두 번째 항은 0과 1로 고정이다.

위 코드 Fibonacci() 메서드를 보고 return Fibonacci(a - 1) + Fibonacci(a - 2); 을 이해해 보자.

또 예시를 5로 들어보겠다.

※ 그림 출처: https://st-lab.tistory.com/94

 

이런 식으로 재귀를 하면 된다.