1003번-피보나치함수

문제

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

1003번: 피보나치 함수

---

접근방법

1) 접근 사고

피보나치 함수에서 재귀되는 경우에 0과 1이 몇 번 나오는지 물어보는 문제이나 반복된 재귀를 사용할 경우 시간초과 발생

 

2) 시간 복잡도

시간복잡도를 줄이기 위해 공통된 규칙이 있는 DP 방법을 탐색

n= 0 일 때

zero는 1개 나오고 one은 0개 나온다

n= 1 일 때

zero는 0개 나오고 one은 1개 나온다

n= 2 일 때

zero는 1개 나오고 one은 1개 나온다

n= 3 일 때

zero는 1개 나오고 one은 2개 나온다

n= 4 일 때

zero는 2개 나오고 one은 3개 나온다

 

이를 통해 점화식이 cache[i] = cache[i - 1] + cache[i - 2]이며 0의 개수는 cache[n - 1]이고 1의 개수는 cache[n - 2]임을 알 수 있다.

3) 배운 점

기본적인 DP 점화식인거 같다.

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
int cache[41];
int main(void)
{
    fastio;
    int t, n;
 
    cin >> t;
 
    cache[0] = 0;
    cache[1] = 1;
 
    for(int i = 2; i < 41; i++)
        cache[i] = cache[i - 1] + cache[i - 2];
 
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
 
        if(n == 0)
            cout << 1 << " " << 0<< "\n";
        else if(n == 1)
            cout << 0 << " " << 1 << "\n";
        else
            cout << cache[n - 1] << " " << cache[n] << "\n";
    }
    return 0 ;
}