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

문제: www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

문제풀이

 

fibonacci(N) 일 때의 0과 1을 각각 몇 번씩 호출하는지를 물어보는 문제이다.

 

fibonacci(N)은 fibonacci(N-2) + fibonacci(N-1) 을 호출하기 때문에 우리가 피보나치 수열을 구할 때 앞의 두 수의 합을 구하듯이 0과 1의 호출 또한 앞선 두 수의 합을 구하면 된다.

이때 N은 40과 작거나 같은 자연수이므로 벡터를 41의 크기로 선언하여 0과 1의 호출 수를 저장하였다.

 

		0 호출	1 호출
fibonacci(0)	0	1	0
fibonacci(1)	1	0	1
fibonacci(2)	fibonacci(0) + fibonacci(1)	1	1
fibonacci(3)	fibonacci(1) + fibonacci(2)	1	2
fibonacci(4)	fibonacci(2) + fibonacci(3)	2	3

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    vector<pair<int, int>> v(41); //41 크기 벡터 선언
    
    v[0].first = 1; //pair의 first는 0호출수
    v[0].second = 0; ///pair의 second는 1호출수

    v[1].first = 0;
    v[1].second = 1;

    for(int i=2; i<=40; i++){ //v[0]~v[40]까지 호출수 저장
        v[i].first = v[i-2].first + v[i-1].first; 
        v[i].second = v[i-2].second + v[i-1].second; 
    }

    int T;
    cin>>T;

    for(int i=0; i<T; i++){
        int num;
        cin>>num;
        cout<<v[num].first<<" "<<v[num].second<<"\n"; //해당 수의 호출수 출력
    }

    return 0;
}

 

 

결과