[백준OJ] #1003 ; 피보나치 함수

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
/*피노나치 수열
/ 1 1 2 3 5 8 ...
/ fibo(3) = fibo(2) + fibo(1) = fibo(0) + fibo(1) + fibo(1)
/ fibo(4) = fibo(3) + fibo(2) = fibo(2) + fibo(1) + fibo(1) + fibo(0) = fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0) = fibo(1)*3 + fibo(0)*2
/ fibo(1) -> retrun 1 하면 됨.
*/
int cntz = 0, cnto = 0;

int fibo(int n)
{
	if (n == 0) { return 0; cntz++; }
	else if (n == 1) { return 1; cnto++; }
	else return fibo(n - 2) + fibo(n - 1);
}
int main()
{
	int n, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &m);
		fibo(m);
		printf("%d %d", cntz, cnto);
	}
}

문제점 : 시간초과가 뜸.

   - 피보나치 같은 경우 계속 중복된 값을 불러오기에, 시간복잡도가 큼.

해결: DP(동적계획법)활용

성공코드보기

2019/01/07 - [success] - [백준OJ] #1003 ; 피보나치 함수 (success)