백준 2748번 피보나치 수 2

< 백준 2748번 피보나치 수 2 - 마포 코딩박 >

사용한 알고리즘: DP


 N (<=90) 번째 피보나치 수를 구하는 문제입니다.

문제풀이는 다음과 같습니다.
(1) (코드: Fibo[91])
 피보나치 수를 저장할 배열을 하나 만든다.

(2) (코드: 9~13)
 Fibo[0] = 1 , Fibo[1] = 1, Fibo[2] = 2 로 초기 설정해 준뒤, i=3 부터 90까지
 Fibo[i] = Fibo[i-1] + Fibo[i-2] 의 점화식을 통해 피보나치 수를 미리 구해줍니다.

(3)
 구하고자하는 N번째가 입력으로 주어지면 과정 (2) 에서 구해놓은 값을 출력해줍니다.

 DP를 배움에 있어서 가장 기본적인 문제인 것 같습니다.
 주의할 점은 피보나치수를 저장할때 long long 배열을 사용하는 점입니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	ll Fibo[91];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	Fibo[0] = 0LL;
	Fibo[1] = 1LL;
	Fibo[2] = 1LL;
	for (int i = 3; i <= 90; ++i)
	Fibo[i] = Fibo[i-1]+Fibo[i-2];
	int N;
	cin >> N;
	cout << Fibo[N] << '\n';
	return 0;
	}

view raw BOJ 2748.cpp hosted with ❤ by GitHub