백준 2748 - 피보나치 수 2

문제 번호: 2748

문제 제목: 피보나치 수 2

문제 주소: https://www.acmicpc.net/problem/2748

문제 내용

입력에 n번째에 해당하는 피보나치 수를 출력한다.

테스트 케이스

1	1
2	1
3	2
10	55
90	2880067194370816120

문제 풀이

입력 범위인 90번째의 수가 매우 크므로 결과 출력에는 64bit 변수가 필요하다.
피보나치 수열의 경우 f(n-1) + f(n-2)로 표현되는 것이 일반적이지만 이를 재귀함수로 구현할 경우 같은 중복 계산이 매우 많아지므로 수가 커질수록 성능이 크게 저하된다. 차라리 for를 이용한 반복문을 이용하는 편이 빠르다.

동적 계획법으로 풀 경우에는 해당하는만큼 배열을 생성하고 아래와 같이 진행하면 된다.
1. n + 1개짜리 배열을 생성하고 [1]과 [2]에는 각각 1을 대입한다.
2. [2]~[n]까지 [n-1], [n-2]를 합한 수를 대입한다.
3. n번째 값을 출력한다.

풀이 코드

#include <iostream>
using namespace std;
// 동적 계획법
void BAEKJOON_2748()
{
	uint64_t n;
	cin >> n;

	if (n == 1 || n == 2)
	{
		cout << 1 << endl;
	}
	else
	{
		uint64_t* fib = new uint64_t[n];
		fib[0] = 1;
		fib[1] = 1;
		for (int i = 2; i < n; i++)
		{
			fib[i] = fib[i - 1] + fib[i - 2];
		}
		cout << fib[n - 1] << endl;
		delete[] fib;
	}
	return;
}

#include <iostream>
using namespace std;
// 반복문 풀이
void BAEKJOON_2748()
{
	uint64_t n;
	cin >> n;

	uint64_t fib = 0;
	if (n == 1 || n == 2)
	{
		fib = 1;
	}
	else
	{
		uint64_t fib1 = 1;
		uint64_t fib2 = 1;
		fib;
		for (int i = 3; i <= n; i++)
		{
			fib = fib1 + fib2;
			fib1 = fib2;
			fib2 = fib;
		}
	}
	cout << fib << endl;
	return;
}