백준 온라인 저지 | 10870번 피보나치 수5 | C++

백준 온라인 저지 | 10870번 피보나치 수5 | C++

10870번: 피보나치 수 5

 

1. 문제 접근

 수학에서 피보나치(fibonacci) 수는 첫째 항과 둘째 항이 1이고 그 이후의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수 Fn의 초항은 F(1) = F(2) = 1이고, 점화식은 F(n) = F(n-1) + F(n-2) (n ≥ 2)으로 나타낼 수 있다. 예를 들어 F(4)는 F(3) + F(2) = F(1) + F(2) + F(2) = 1 + 1 + 1 = 3이다. 재귀 문제를 풀 때 생각해야 할 함수 인자, 기본 조건, 그리고 재귀 조건을 살펴보자.

 

■ 1.1 함수 인자

 피보나치 수의 점화식 F(n) = F(n-1) + F(n-2) (n ≥ 2)을 보면 피보나치를 계산하기 위해서 필요한 숫자는 양의 정수 N임을 알 수 있다. 그러므로 재귀 함수에 전달할 인자는 사용자가 입력할 양의 정수 N이다.

 

■ 1.2 기본 조건

 피보나치 수는 점화식의 초항이 주어져 있다. 초항 F(1)과 F(2)가 1로 주어져 있으므로 팩토리얼의 기본 조건은 n이 1과 2일 때 1을 반환하도록 구현해야 한다.

 

■ 1.3 재귀 조건

 피보나치 수의 점화식 F(n) = F(n-1) + F(n-2) (n ≥ 2)은 양의 정수 n에서 각각 1과 2만큼 감소시킨 값을 재귀 함수의 인자로 전달하여 호출하고, 각 재귀 함수에서 반환된 값을 더하는 방식으로 구현할 수 있다.

 

2. 문제 풀이

1. 재귀 함수 fibonacci를 정의한다.
   • 매개 변수로 전달할 인자는 사용자가 입력한 양의 정수인 n이다.
2. 기본 조건을 구현한다.
   • n이 1 또는 2인 경우, 1을 반환한다.
3. 재귀 조건을 구현한다.
   • n이 1 또는 2가 아닌 경우, n - 1, n - 2를 인자로 각각 전달한 재귀 함수를 호출한다.
   • 두 재귀 함수에서 반환된 값을 더해 반환한다.

 

3. 문제 해결

#include <iostream>
using namespace std;

int fibonacci(int n);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin >> N;
	cout << fibonacci(N) << '\n';
	return 0;
}

int fibonacci(int n) {
	// 기본 조건입니다. 0번째, 1번째 피보나치 수는 각각 0, 1입니다.
	if (n == 0 || n == 1) {
		return n;
	}
	// 재귀 조건입니다. Fn = Fn-1 + Fn-2 (n >= 2)입니다.
	else {
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

10870번 피보나치 수5 성공

 

4. 문제 고찰

 피보나치 수도 팩토리얼과 마찬가지로 기본적인 재귀 함수 문제이다. 점화식과 초항이 주어져 있어서 문제를 파악하는 게 훨씬 쉬웠다.