[백준 2747] 피보나치 수 (C/C++)

 

Problem

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

2747번: 피보나치 수

 

Comment

피보나치 수를 재귀 함수만 사용하게 된다면 시간 복잡도가 $O(2^n)$이 되어 시간 초과가 날 확률이 높습니다. 따라서 배열에 피보나치 함수들의 값을 저장해 실행 시간을 줄이는 것이 가장 중요합니다.

 

Code

#include <stdio.h>

int n, d[50] = { 0, 1 };

int fib(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (d[n] != 0) return d[n];

	d[n] = fib(n - 2) + fib(n - 1);
	return d[n];
}

int main()
{
	scanf("%d", &n);
	printf("%d", fib(n));
}

 

Result