[백준 알고리즘/BOJ/C++] 1003 피보나치 함수

 

 

피보나치 함수를 호출했을 때 0과 1을 각각 몇 번 호출하는지 출력하는 문제다

​

처음엔 시간제한이 있는 줄 모르고 신나게 위 함수에서 printf를 지우고

0과 1을 return 할 때마다 만들어둔 변수에 +1 해준 뒤 최종 return시 그 변수의 값을 출력하는 형태로 짰다

결과는 나오지만 당연히 시간초과...

​

규칙부터 찾아야 할 것 같다

 

0 ~ 8 입력했을 때 출력값

 

​0부터 차례대로 입력해 보면 결과가 피보나치 수열 그 자체임을 알 수 있다 (?)

0이 호출된 횟수는 N-1번째 피보나치 수, 1이 호출된 횟수는 N번째 피보나치 수다 (N!=0)

 

이제 코딩은 더 쉽다

 

 

#include <iostream>
using namespace std;
 
int main() {
    int t, n;
    long long f[41];
 
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        if(n==0)
            cout << 1 << ' ' << 0 << "\n";
        else {
            f[0] = 0;
            f[1] = 1;
 
            for (int i = 2; i <= n; i++) {
                f[i] = f[i - 1] + f[i - 2];
            }
 
            cout << f[n - 1] << ' ' << f[n] << "\n";
        }
    }
}

 

이제 시간 초과는 되지 않지만 N이 입력될 때마다 피보나치 수를 구하게 되므로 좀 아쉽다

미리 구해놓고 불러다 쓰면 더 빠를 것 같아서 또 수정

 

 

#include <iostream>
using namespace std;
 
int main() {
    int t, n;
    long long f[41];
 
    cin >> t;
 
    //피보나치 수열 구해놓기
    f[0] = 0;
    f[1] = 1;
 
    for (int i = 2; i <= 40; i++)
        f[i] = f[i - 1] + f[i - 2];
 
    while (t--) {
        cin >> n;
 
        if(n==0)
            cout << 1 << ' ' << 0 << "\n";
        else
            cout << f[n - 1] << ' ' << f[n] << "\n";
    }
}

 

깔끔