cpp) 백준 1003: 피보나치 함수

Problem

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

fibonacci(3)의 경우 1은 2번 출력되고, 0은 1번 출력된다. fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

 

 

Solution

매번 재귀함수를 호출해서 수를 구한다면 시간 초과가 뜨기 때문에 규칙성을 찾아 문제를 해결해야 한다. 과정을 짚어보면, '0 호출 횟수'와 '1 호출 횟수' 모두 기존의 피보나치 함수와 유사한 것을 확인할 수 있다.

 

n	피보나치 수	0 호출 횟수	1 호출 횟수
0	0	1	0
1	1	0	1
2	1	1	1
3	2	1	2
4	3	2	3
5	5	3	5
6	8	5	8
7	13	8	13
8	21	13	21
k	fibo(k-1) + fibo(k-2)	fibo(k-1)	fibo(k)

 

#include<iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

    int T,N;
    cin >> T;

    int dp[41] = {0,1,};
    
    for(int i=2;i<=41;i++){
        dp[i] = dp[i-1] + dp[i-2];  
    }

    for(int i=0;i<T;i++){
        cin >> N;
        if (N==0)
            cout << 1 << ' ' << 0 << '\n';
        else if (N==1)
            cout << 0 << ' ' << 1 << '\n';
        else
            cout << dp[N-1] << ' ' << dp[N] << '\n';
    }
    
   return 0;
}

 

편의를 위해, N이 0 또는 1인 경우는 값을 미리 정하고 시작했다.

 

 

Reference

https://gaeunhan.tistory.com/69

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