[백준] 10870번 피보나치 수

 

[21-04-20]

 

---

문제

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

분석

이 문제 또한 피보나치 자체의 개념을 알면 금방 풀 수 있는 문제다. (문제에도 나와있음)

N번째 숫자는 N-1번의 숫자와 N-2번의 숫자를 더한 값이다.

ex) 7번째 수 : 13 = 5(5번째 수) + 8(6번째 수)

피보나치 수열 > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

이때 n-1의 수를 구하려고 한다면 n-1의 숫자 또한 ( n-1)-1번째 수와 (n-1)-2번째 수를 더한 값이라는 것을 알 수 있다.

 

또한 입력 범위에 0이 포함되어 있고, 0번째 피보나치 수는 n-1 + n-2의 피보나치 수로 구할수가 없다.(기저사례)

 

 

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(Fibonacci(n));
	}
	
	public static int Fibonacci(int n) {
		if(n==0) {
			return 0;
		} else if(n<=2) {
			return 1;
		}
		
		return Fibonacci(n-1) + Fibonacci(n-2);
	}

}

 

 

 

결과

 

 

 

 

---