DP_2748

문제 출처: https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

우선 Fn = Fn-1 + Fn-2 (n>=2)의 식을 이용하여 재귀함수로 작성하면 아래와 같다.

 

#include <iostream>

using namespace std;

int Fib(int N) {

	if (N < 2) {
		if (N == 1) {
			return 1;
		}
		else {
			return 0;
		}
	}

	return Fib(N - 1) + Fib(N - 2);

}

int main() {

	int N;

	cin >> N;
	cout << Fib(N);

}

 

DP를 사용하지 않은것에 비해 시간이 오래걸리기 때문에, 시간 제한에 걸려 오답이 나오게 된다. 따라서 동적 계획법을 적용하여 문제를 풀이하도록 한다.

 

DP 중에서도 간단한 문제인데, 단순히 한번 연산했던 결과를 DP라는 array에 저장해두고, 필요할 때 다시 쓴다는 개념으로 이해하면 된다. 90까지의 피보나치 수열은 int로 다 담을 수 없을 만큼 크기 때문에, long long형 배열 dp[100]을 선언한다.

 

#include <iostream>

using namespace std;

long long dp[100] = {0};

void Fib(int N) {

	dp[0] = 0;
	dp[1] = 1; // 피보나치 수열에서 0번째, 1번째는 각각 0과 1이다.

	for (int i = 2; i <= N; i++) { // 0과 1은 이미 저장되어 있으므로
								   // N번째 까지 계산한다.
		dp[i] = dp[i - 1] + dp[i - 2]; // 각 연산 결과를 dp 배열에 저장해둔다.
	} 

}

int main() {

	int N;

	cin >> N;
	Fib(N);
	cout << dp[N];
}