백준 - 10870 c++ 풀이 및 설명

안녕하세요 오늘은 백준알고리즘의 10870번을 풀어보도록 하겠습니다.

 

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-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번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

음,

즉 10을 입력했을 시 55가 출력이 되어야 합니다.

 

소스코드 보시죠

#include <iostream>

using namespace std;

int fib(int num)
{
    if (num == 0 ) 

    {
        return 0;
    }
    else if(num == 1)
    {
         return 1;
    }
    else
    {
        
        return fib(num - 1) + fib(num -2);
    }
    
    
    
}

int main()
{   
    int num;
    cin >> num;
    cout<<fib(num)<<endl;
    return 0;

}

 

풀이

여기서 중요하게 생각할 것이

elese { return fib(num -1 ) + fib(num - 2) } 이 부분입니다.

0이면 0

1이면 1

2 이면  =  그전 숫자와 더해서  1+1 = 2 // 이제 그전숫자와 더해야 된다.

 2 + 3 = 5

5 + 3 = 8

5 + 8 = 13

8 + 13 = 21

21 + 13 = 34

21 + 34 = 55

34 + 55 = 89

 

즉,, fib(3)를 구할 때는

fib(3-2) + fib(3-1) 인데  fib(1) + fib(2) 이다.

 

fib(5)를 구할 떄는

fib(2) + fib(3) 이다.