[백준/14495] 피보나치 비스무리한 수열

주소

https://www.acmicpc.net/problem/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번째 피보나치 비스무리한 수를 출력한다.

 

예제 입력 1

10

 

예제 출력 1

19

 

풀이

dp 사용해서 풀면 된다.

vector<int>로 선언했더니 int 범위를 넘어가서 틀렸다.

숫자가 클 것 같으면 long long으로 선언하는 것을 잊지 말자.

 

코드

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;

    if (n <= 3) {
        cout << 1;
        return 0;
    }

    vector<long long> v(n + 1, 0);
    v[1] = v[2] = v[3] = 1;

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

    cout << v[n];

    return 0;
}