[알고리즘] 백준 10870번 "피보나치 수 5" (C/C++) - Don 임베디드

문제요약:

 

피보나치 수는 0, 1로 시작한다. 0번째 피보나치 수는 0, 1번째 피보나치 수는 1이다.

그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

식으로는, F(n) = F(n-1) + F(n-2),  (n >= 2) 가 된다.

 

n=17일 때까지 피보나치 수는 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하라.

*반드시 재귀함수를 사용해보자.

 

 

제약:

 

시간 제한 1초, 메모리 256MB

0 <= n <= 20, n은 정수.

 

예제 1 입력.	예제 1 출력.
0	0
예제 2 입력.	예제 2 출력.
1	1
예제 3 입력.	예제 3 출력.
10	55

 

 

정답코드:

#include <iostream>
 
using namespace std;
 
int Fibonacci(int n)
{
    if ((n == 0) || (n == 1))   // Fibo[0] = 0, Fibo[1] = 1.
    {
        return n;
    }
    else if ((1 < n) && (n <= 20))
    {
        // Fibo[n-2] 와 Fibo[n-1]을 계산한 값을 return.
        return Fibonacci(n - 2) + Fibonacci(n - 1);
    }
    else
    {
        return -1;    // 문제에서 정의되지 않은 Case.
    }
}
 
int main()
{
    int N;
    int nResult;
 
    // N을 입력 받음.
    cin >> N;
 
    // 재귀함수로 피보나치 계산.
    nResult = Fibonacci(N);
 
    // 계산한 결과 출력.
    cout << nResult << '\n';
 
    return 0;
}

 

원본 링크: https://www.acmicpc.net/problem/10870