피보나치 수 5 백준 10870번 c++

문제 링크 

n 번째 피보나치수를 구하는데, 20이하 번째만 구하면 된다. 

수의 크기가 작아서 재귀함수로 풀어도 가능하고. DP 메모이제이션으로 풀어도 통과한다. 

 

“맞았습니다”코드 1 

#include <bits/stdc++.h>
using namespace std;

long long D[22];
int n;

long long fibo(int num){
  if (num == 0) return 0;
  if (num == 1) return 1;
  return fibo(num-1) + fibo(num-2);
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  cout << fibo(n);
  return 0;
}

 

“맞았습니다" 코드2

#include <bits/stdc++.h>
using namespace std;

long long D[22];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  D[1] = D[2] = 1;
  for(int i = 3; i <= n; i++){
    D[i] = D[i-1] + D[i-2];
  }

  cout << D[n];
  return 0;
}