[백준]1003-피보나치 함수(Dynamic Programming)

그냥 n번째 피보나치 수를 계산하는 문제가 아니다.

n번째 피보나치 수를 재귀 함수로 구할 때, fib(0)과 fib(1)이 몇 번씩 호출되는지를 묻는 문제다.

 

근데 딱히 다를 건 없다. 동적 계획법으로 푸는데, 누적하는 수가 피보나치 수가 아니라 0과 1의 회수일 뿐이다.

//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
void fib(int n);
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        fib(num);
    }
}
 
void fib(int n) {
    if (n == 0) {
        cout << 1 << " " << 0 << endl;
        return;
    }
    else if (n == 1) {
        cout << 0 << " " << 1 << endl;
        return;
    }
 
    pair<int, int> num1, num2, num3;
    num1.first = 1; num1.second = 0;
    num2.first = 0; num2.second = 1;
 
    for (int i = 2; i <= n; i++) {
        num3.first = num1.first + num2.first;
        num3.second = num1.second + num2.second;
        num1.first = num2.first;
        num1.second = num2.second;
        num2.first = num3.first;
        num2.second = num3.second;
    }
    cout << num3.first << " " << num3.second << endl;
    return;
}

pair<int, int>를 사용했다. 코드를 보면 이해가 갈 것이다.