[성실코딩 3일차] 백준 #1003 피보나치 함수 / DP &s

fib(n)이 호출되고 fib(n-1), fib(n-2)가 각각 호출되고 그에 따른 0과 1이 출력되는 과정을

bst tree모양으로 그리면 직감적으로 더 느낄 수 있음!!

0과 1이 호출되는 횟수도 똑같이 피보나치 함수 구조를 가지고 있음

#include<iostream>

using namespace std;

int fib0[41] = {1,0,};
int fib1[41] = {0,1,};

int getfib0(int n) {
	int pre = fib0[0];
	int cur = fib0[1];

	int res = fib0[1];

	// 0,1같은 경우에는 따로 처리해주기
	if (n == 0 || n == 1) {
		return fib0[n];
	}

	for (int i = 2; i <= n; i++) {
		// 다른 테이스케이스 때 여길 채웠다면
		if (fib0[n]!=0) { 
			return fib0[n];
		}
		res = pre + cur;

		pre = cur;
		cur = res;
		fib0[i] = res;
	}
	return res;
}

int getfib1(int n) {
	int pre = fib1[0];
	int cur = fib1[1];

	int res = fib1[1];

	// 0,1같은 경우에는 따로 처리해주기
	if (n == 0 || n == 1) {
		return fib1[n];
	}

	for (int i = 2; i <= n; i++) {
		if (fib1[n] != 0) {
			return fib1[n];
		}
		res = pre + cur;

		pre = cur;
		cur = res;
		fib1[i] = res;
	}
	return res;
}

int main(void) {

	int tc;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		int temp;
		cin >> temp;

		cout << getfib0(temp) << " " << getfib1(temp) << endl;
	}

	return 0;
}

---

5개월만에 다시 풀었당

DP 사용해서 똑같은 방법인데 이번에 푼 코드가 더 직관적으로 이해하기 쉬운 것 같다!

메모리나 시간 면에서는 똑같은 성능을 보인다.

#include < iostream >

using namespace std;

int table_0[41]={0,};
int table_1[41]={0,};

int fib_0(int _num){
    // 탈출조건
    if(_num==0){
        return table_0[_num]=1;
    }else if(_num==1){
        return table_0[_num]=0;
    }
    
    // recursive
    if(table_0[_num]!=0) return table_0[_num];
    else return table_0[_num]={fib_0(_num-1)+fib_0(_num-2)};
}

int fib_1(int _num){
    // 탈출조건
    if(_num==0){
        return table_1[_num]=0;
    }else if(_num==1){
        return table_1[_num]=1;
    }
    
    // recursive
    if(table_1[_num]!=0) return table_1[_num];
    else return table_1[_num]={fib_1(_num-1)+fib_1(_num-2)};
}

int main(void) {

    int tc;
    cin >> tc;
    for(int t=1; t < =tc; t++){
        int num;
        cin>>num;
        
        cout << fib_0(num) << ' ' << fib_1(num) << endl;
    }
    return 0;
}