[BOJ14495][C++] 피보나치 비스무리한 수열

문제

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

 

 

입력

자연수 n(1<=n<=116)이 주어진다.

 

 

출력

n번째 피보나치 비스무리한 수를 출력한다.

 

 

예제 입력 1

10

 

예제 출력 1

19

 

 

힌트

 

 

출처

High School > 선린인터넷고등학교 > 2017 선린 봄맞이 교내대회 I번

· 문제를 만든 사람: leehun456

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream>   using namespace std;   int main() {     int n;     long long eq[120];   // int 자료형 X       /*      * f(n) = f(n-1) + f(n-3)      * (1 <= n <= 116)      * f(1) = 1, f(2) = 1, f(3) = 1      */        for (int i = 0; i <= 116; i++) {          if (i == 0) eq[i] = 0;          else if (i >= 1 && i <= 3) eq[i] = 1;          else eq[i] = eq[i - 1] + eq[i - 3];        // f(n) = f(n-1) + f(n-3)        }        cin >> n;        cout << eq[n] << endl;       return 0; }r

---

피보나치 비스무리한 수열을 담을 배열의 자료형을 int 형식이 아닌 long long 형식으로 선언해야 함에 주의해야 한다.

그래야만 116번째까지의 피보나치 비스무리한 수열을 배열에 담을 수 있다.