백준 1003번 : 피보나치 함수

문제 링크 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 문제 설명 

 

피보나치함수에서 0과 1을 호출하는 횟수를 출력 하면됨 

 

 알고리즘 

 

정답비율이 20%대인데 이해불가 

0과 1을 호출하는 횟수도 피보나치 수열을 이루기때문이다 . 피보나치처럼 dp 로풀면 된다.

 코드 

#include<iostream>
 
using namespace std;
 
 
int dp1[45];
int dp2[45];
 
//0의 갯수 구하는 함수
int func0(int n) {
    if (dp1[n] != -1)return dp1[n];
    if (n == 0)return 1;
    if (n == 1)return 0;
 
    return dp1[n] = func0(n - 1) + func0(n - 2);
 
}
 
//1의 갯수 구하는 함수
int func1(int n) {
    if (dp2[n] != -1)return dp2[n];
    if (n == 0)return 0;
    if (n == 1)return 1;
 
    return dp2[n] = func1(n - 1) + func1(n - 2);
 
}
 
 
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < 45; i++) {
        dp1[i] = -1;
        dp2[i] = -1;
    }
 
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        cout << func0(num) << " " << func1(num) << "\n";
    }
 
}