[C++] BOJ 2747 - 피보나치 수

문제 : http://boj.kr/2747

티어 : 브론즈 3

 

피보나치 수열의 정의는 다음과 같다.

$F_{i}$를 피보나치 수열의 i번째 값이라고 할 때 아래의 식이 성립한다.

 

이를 이용하여 재귀함수로 풀 수 있고, 또는 반복문을 통하여 $O(N)$ 의 시간만큼 피보나치 수열의 i번째 값을 구해 배열에 저장하고,

입력에 주어진 인덱스를 통하여 $O(1)$ 의 시간만에 구하는 방법이 있다.

이를 코드로 작성하면 다음과 같다.

int N;
cin >> N;
F[1]=1;
F[2]=1;
for(int i=3; i<=45; i++) {
	F[i]=F[i-1]+F[i-2];
}
cout << F[N];