[백준] [C++] 2747번 피보나치 수

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

2747번: 피보나치 수

---

코드

#include <iostream>
using namespace std;

int Fibonacci(int n) {
	int num[45] = { 0, 1, };
	
	for (int i = 2; i <= n; i++) {
		num[i] = num[i - 1] + num[i - 2];
	}

	return num[n];
}

int main() {
	int a;
	cin >> a;
	cout << Fibonacci(a);

	return 0;
}

---

풀이

정수 입력 a를 입력받아 피보나치 수의 a번째 수를 출력하는 문제이다. (이때 정수 a는 45보다 작거나 같은 자연수이다.)

 

피보나치수열은 바로 전 두 수의 합을 표현하는 함수로 F(n) = F(n-1) + F(n-2)로 표현한다.

 

이때 주의할 점은 F(0) = 0이고 F(1) = 1이다.

 

피보나치수열을 재귀 함수 형식으로 만들면 시간 초과가 떠서 입력 조건에 맞추어 배열로 구현하였다.

 

배열의 0번째 인덱스에는 0을, 1번째 인덱스에는 1을 넣어 초기화하였고 2번째 인덱스부터는 이전 두 수를 더하여 배열에 저장하는 방식을 사용하였다.