[BOJ S4][C++] 백준 14495번: 피보나치 비스무리한 수열

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

14495번: 피보나치 비스무리한 수열

 

문제

피보나치 비스무리한 수열은 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번째 피보나치 비스무리한 수를 출력한다.

 

풀이

맞게 한 것 같은데 틀렸다고 뜨면 long long 범위를 생각하자

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<long long> fibo(n+1, 1);
    for(int i=4; i<=n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-3];
    }
    
    cout << fibo[n];
    
    return 0;
}

/*
 */