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

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

DP 유형의 문제입니다.

Top-Down 방식을 이용해서 피보나치 함수를 구현한 후, 피보나치 함수의 값, 0이 나오는 갯수, 1이 나오는 갯수 이 세가지의 규칙을 찾아내면 되는 문제였습니다. 이 세가지의 규칙은 다음과 같습니다.

 

피보나치 함수	0이 나오는 갯수	1이 나오는 갯수
0	1	0
1	0	1
2	1	1
3	1	2
4	3	4

 

n의 값이 2이상일 때 부터 0이 나오는 갯수는 F(n - 1), 1이 나오는 갯수는 F(n) 과 같다는 것을 확인할 수 있습니다.

 

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

int dp[41];

int F(int n) {
    if(n == 0) return dp[0] = 0;
    else if(n == 1) return dp[1] = 1;
    else if(dp[n] != -1) return dp[n];
    else return dp[n] = F(n - 2) + F(n - 1);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        memset(dp, -1, sizeof(dp));
        int n;
        cin>>n;
        F(n);
        if(n == 0) cout << "1 0\n";
        else if(n == 1) cout << "0 1\n";
        else cout << dp[n - 1] << " " << dp[n] << "\n";
    }
}