[BOJ-10870][C++] 피보나치 수 5

문제

피보나치 수는 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`번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 `n`이 주어진다. `n`은 20보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

예제 입력 1 

10

 

예제 출력 1

			
			
			
		
55

 

알고리즘 분류

• 수학
• 구현

 

문제 출처

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

10870번: 피보나치 수 5

 

---

 

문제 해결 방법

• 재귀 함수를 이용하여 피보나치 수를 구현하였다.

			
			
			
		
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• 피보나치 수와 관련된 내용은 이곳을 참고한다.

6번째 피보나치 수를 재귀 함수를 이용하여 구할 경우 ⓒMedium

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}
 
int n;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    cout << fibonacci(n) << '\n';
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [재귀]
• 브론즈II