[백준 2747] 피보나치 수

• 안녕하세요. BlockDMask 입니다.

0. 제목

• 백준 2747 피보나치 수

• BOJ 2747 피보나치 수 

1. 문제설명

피보나치의 수

n=0 일때 0

n=1 일때 1

이다.

피보나치의 수를 11개 까지 나열해 보면

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

이때 45보다 적은 정수 NUM이 들어오면

n 이 NUM 일때 피보나치 수를 구하여라.

2. 풀이과정

recursive function(재귀함수)로 구현을 했는데

역시 시간초과가 나서 iterative (반복문)을 이용하여 피보나치 수를 구현했습니다.

처음에는 반복문으로 구현한 피보나치 함수에서 변수를 여러개 선언해서 구현을 했는데

코드가 지저분해 보여서 int 형 배열을 선언해서 구했습니다.

여러개의 변수를 이용하여 구현한 반복문 기반 피보나치 코드는 

//for 문

int Fibonacci(int n){

    int a=0;

    int b=1;

    int tmp;

    if(n == 1) return 1;

    if(n == 0) return 0;

    for(int i=0 ; i<n-1; i++){

        tmp = b;

        b = a+b;

        a = tmp;

    }

    return b;

}

이거였습니다. (변수가 지저분하게 더해지고 해서 배열을 이용하여 깔끔하게 정리했습니다. 맞긴 맞았습니다 이것도)

반복문을 이용한 피보나치로 풀어야 문제가 풀리고

재귀함수를 이용한 피보나치 수는 시간초과가 납니다.

두개의 코드 다 적어 놓겠습니다.

3. 코드

#include <iostream>
using namespace std;
 
// Fn = F(n-1) + F(n-2); (n>=2)
 
/*
//recursive
int Fibonacci(int n){
    if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}
*/
 
//iterative (for 문)
int Fibonacci(int n){
    int arr[3] = {0,1,1};
    for(int i=2 ; i<n; i++){
        arr[(i+1)%3] = arr[i%3] + arr[(i-1)%3];
    }
    return arr[n%3];
}
 
int main(void){
 
    int num;
    cin >> num;
    cout << Fibonacci(num);
    
    return 0;
}

4. 인증

감사합니다.