피보나치 함수 #1003 c++ 풀이

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

1003번: 피보나치 함수

 

0.25 초 (추가 시간 없음) 를 보고, 수업시간에 피보나치 수열계산을 재귀로 풀게 되면 시간이 오래걸린다고 했던 것이 기억에 남는다. 

 

최소한 반복문이나 dp로 풀어야겠다고 생각을 했다.

 

dp란 

dp란 메모이제이션을 이용하여, 하나의 문제는 한번만 풀도록 구현하는 방법이다.

dp로 피보나치를 구현하는 방법은 다음과 같다.

 

using namespace std;
long long fiboarr[100] = {0,1,};
long long fibo(int N)
{
    if(N == 0 || N == 1)
        return fiboarr[N];
    else if(fiboarr[N] == 0)
        fiboarr[N] = fibo(N-1) + fibo(N-2);
    return fiboarr[N];
}
int main() {
    int N;
    cin >> N;
    cout << fibo(N);
}

fiboarr에 N까지 모든 피보나치 수열을 저장하는데, 이미 저장되어있다면 기존에 구해놓은 값을 리턴하는 방법이 바로 dp이다.

 

#include<iostream>
#include<vector>


using namespace std;


/*
1. dp 테이블 정의
2. dp table 초기화
3. 규칙 찾아서 적용
4. 출력
*/
int count0 = 0;
int count1 = 0;
long long fibo[41] = {0,1,};

long long fibonacci(long long n) {
    if (n == 0) {
        return fibo[n];
    }
    else if (n == 1) {
        //printf("1");
        return fibo[n];
    }
    else if(fibo[n]==0){
        fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }
    return fibo[n];
}
int main() {

    int T;
    cin >> T;
    int tmp;
    for (int i = 0; i < T; i++)
    {
        cin >> tmp;
        if (tmp == 0)
            cout << "1 0" << '\n';
        else
            cout << fibonacci(tmp - 1) << ' ' << fibonacci(tmp) << '\n';
    }

	return 0;
}

최종코드