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

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

---

문제가 풀리는 가장 간단한 방법으로 풀었더니 시간초과가 떴다

#include <iostream>

using namespace std;

int z, o;

int fibonacci(int n) {
    if (n == 0) {
        z++;
        return 0;
    } else if (n == 1) {
        o++;
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main()
{
    int t, n;
    cin >> t;
    
    for(int i=0; i<t; i++){
        z = 0;
        o = 0;
        
        cin >> n;
        fibonacci(n);
        
        cout << z << " " << o <<"\n";
    }
    
    
    
    return 0;
}

다이나믹 프로그래밍을 사용해서 풀어야했던 것... 

 

---

DP를 사용하려면 규칙을 찾아야하는 데

 

n=0 일 때, 1 0 (0 한번 호출, 1 호출 x)

n=1 일 때, 0 1

n=2 일 때, fib(1) + fib(0) 니까 1 1

n=3 일 때, fib(1) + f(2) => f(1) + f(1) + f(0) 이니까 1 2

n=4 일 때, fib(2) + fib(3) => {fib(1) + fib(0)} + {fib(1) + f(1) + f(0)} 이니까 2 3

 

여기까지 구하다 보니까 0 1의 호출 횟수도 피보나치처럼 더해진다는 것을 알게 됨!

 

이 규칙을 사용해서 코드를 짜주니까 맞았당

 

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int T, m;
    vector<pair<int, int>> v;
    
    cin >> T;
    
    v.push_back({1,0});
    v.push_back({0,1});
    
    int a, b;
    for(int i=2; i<=40; i++){
        a = v[i-1].first + v[i-2].first;
        b = v[i-1].second + v[i-2].second;
        v.push_back({a,b});
    }
    
    for(int i=0; i<T; i++){
        cin >> m;
        cout << v[m].first << " " << v[m].second << "\n";
    }

}