알고리즘(C++) / 백준 10870 : 피보나치 수 5

10870

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

문제

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

 

입력

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

 

출력

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

 

코드

//10870 피보나치 수 5
#include <iostream>
using namespace std;

int pivo(int num) {
	if (num == 0)
		return 0;
	if (num == 1)
		return 1;
	return pivo(num - 2) + pivo(num - 1);
}

int main() {
	int n;
	int sum;

	cin >> n;

	sum = pivo(n);

	cout << sum << endl;

	return 0;
}

 

결과

 

설명

재귀함수를 사용하여 문제를 해결하였다.

pivo라는 재귀 함수를 사용하여 n-1번째와 n-2번째를 더하여 n번째를 구할 수 있다. 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1이다. 따라서 조건문으로 0일 때는 0 출력 1일 때는 1을 출력할 수 있다. 

 

고찰

처음 구현하였을 때 재귀함수를 사용하지 않고 for문 만으로 작성하였다. 하지만 이 방법은 문제에서 원하는 방법이 아니었기 때문에 틀렸다.

재귀함수를 사용하여 구하는 문제이기 때문에 재귀함수를 이용하여 코드를 다시 작성할 수 있었다. 

어렵지 않게 구현할 수 있었다.