다이나믹프로그래밍1 - 백준 2748번 피보나치 수 2

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

IDEA

피보나치 수열은 재귀로도 풀 수 있지만 이 문제는 재귀로 풀면 시간초과가 난다. 

그 이전 수들이 모여 그 다음 수들을 만들 수 있으므로 DP로 풀 수 있다.

DP의 기본격인 피보나치는

fibo[0] = 0

fibo[1] =1

fibo[n] = fibo[n-1] + fibo[n-2]  (n >=2)

라는 점화식을 따라가면 된다. 

 

문제에 90보다 작거나 같은 수라고 써있다. 

90번째 피보나치 수는 int형 범위를 벗어나기 떄문에 long long 을 이용해주어야한다. 

 

코드

#include <iostream>
using namespace std;

long long arr[91] = { 0 };

int main() {
	arr[1] = 1;
	int n;
	scanf("%d", &n);
	for (int i = 2; i < n+1; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	printf("%lld\n", arr[n]);
}