[BOJ / C++] 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번째 피보나치 비스무리한 수를 출력한다.

Solved.ac 레벨

실버 IV

풀이

#include <bits/stdc++.h>
#define MAX 117

using namespace std;

int n;
long long dp[117];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    for(int i = 1; i <= 3; i++){
        dp[i] = 1;
    }

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

    cout << dp[n] << '\n';

    return 0;
}

피보나치 수열과 동일한 방법으로 접근하면 된다.

다만 dp[1] ~ dp[3]은 모두 1인 것과 피보나치 수열에서도 그렇듯, dp 배열에 들어갈 수 있는 값의 범위를 잘 생각하여야 한다.

 

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