백준 2748번 피보나치 수 2

#2748. 피보나치 수 2

문제링크

Problem

  • Goal : n번째 피보나치 수를 구하여라
  • condition
    • 최대 90번째 피보나치 수를 구할 수 있어야 함
    • 시간 제한 1초

Solution

수식 그대로 DP를 적용한다.

1
2
// dp[n]은 n번째 피보나치 수
dp[n] = dp[n-1] + dp[n-2];

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
long long dp[91];
long long fibo(int n)
{
dp[0] = 0, dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

int main()
{
int n;
cin >> n;
cout << fibo(n) << endl;
return 0;
}

주의할 점은 90번째 피보나치 수(10의 18승보다 큼)를 담으려면 long long을 써야 한다는 점이다.(long은 안된다.)