[2748] 피보나치수2

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

정수 n(단, n>=2)이 주어지면 n번째 피보나치 수열 값을 구하는 문제다.

 

첫 번째 풀이 -> 틀림

#include <iostream>

using namespace std;

int Fibonacci(int n);

int main(void) {
	int n;
	cin >> n;
	cout << Fibonacci(n) << endl;
	return 0;
}
int Fibonacci(int n) {
	int f1 = 0, f2 = 1, res = 0;
	for (int i = 2; i <= n; i++) {
		res = f1 + f2;
		f1 = f2;
		f2 = res;
	}
	return res;
}

 

 

틀린 이유

1.문제에서 시간 제한이 1초였다. 이 조건을 제대로 만족시키지 못했다.

2. 데이터 타입. 피보나치 수열은 기하급수적으로 증가한다. int만으로는 감당을 못한다.

 

 

두 번째 풀이

#include <iostream>
using namespace std;

long long fibonacci[91] = { 0,1, };
long long Fibonacci(int n);
int main(void) {
	int n;
	cin >> n;
	cout << Fibonacci(n) << endl;
	return 0;
}
long long Fibonacci(int n) {
	if (n == 0 || n == 1) return fibonacci[n];
	else if (fibonacci[n] == 0) {
		fibonacci[n] =  Fibonacci(n - 2) + Fibonacci(n - 1);
	}
	return fibonacci[n];
}

모르겠어서 다른 사람 풀이를 참고했다. 

시간 제한이 1초이기 때문에 매번 첫 번째 방법처럼 for문을 돌려서 풀기엔 시간이 부족하다.

재귀함수를 사용하는 동시에 계산해둔 값들을 저장해두고 다시 사용하는 방법으로 문제를 해결했다.(이 방법을 DP라고 하는 듯 하다.)

(계산해둔 값을 저장하지 않고 재귀함수만 사용해도 time out이 될 가능성이 있다.)

 

참고 사이트

https://cryptosalamander.tistory.com/80