백준 c++ 2748 "피보나치 수 2" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자 사고]

이 문제는 문제에 점화식이 써져 있어 다이나믹 프로그래밍 알고리즘을 짜기 수월했다.

 

다만 한가지 조심해야 되는 점은 자료형의 크기이다.

 

int형으로 자료형을 선언하게 되면 오버플로우가 발생하여 원하는 값이 소실되는 문제가 생긴다.

 

long형으로 바꾸기 혹은 안전하게 long long으로 해결해도 된다.

 

Fn = Fn-1 + Fn-2 (n ≥ 2)

 

[소스 코드]

#include <iostream>
#include <vector>


using namespace std;

int N;
vector<long long> Dp;

void Input() {
	cin >> N;
	Dp.resize(92);
	Dp[0] = 0;
	Dp[1] = 1;
	Dp[2] = 1;
}

void Solve() {
	for (int i = 3; i <=90; i++) {
		Dp[i] = Dp[i - 1] + Dp[i - 2];
	}
}

int main(void) {
	Input();
	Solve();
	cout << Dp[N];

}