백준 No.2748) 피보나치 수2

n번째 피보나치 수를 구하는 문제이다.

DP를 활용하여 풀면 수월하게 풀 수 있다.

 

DP를 사용하기 위해 우선 점화식을 확인하면

$ F_0 = 0 $

$ F_1 = 1 $

$F_{(n)}=F_{(n-1)}+F_{(n-2)}$               $(n \in\{2,3,...\})$

 

이며 각각

dp[0] = 0

dp[1] = 1

dp[n] = dp[n-1] + dp[n-2]

로 적용하여 변경하면 된다

 

n <= 90 이라는 적은 제한이 걸려있기 때문에

배열에 저장하여 계산하면 쉽게 풀 수 있다.

 

 

해당 코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;
int main()
{	
	int count;

	cin >>  count;

	vector<long long> dp;
	dp.push_back(0);
	dp.push_back(1);

	for (int i = 2 ; i <= count ; i ++)
	{
		dp.push_back( dp[i-2] + dp[i-1]);
	}

	cout << dp[count];
}