[백준 14495번] 피보나치 비스무리한 수열 (C++)

문제링크 : https://www.acmicpc.net/problem/14495

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll arr[117];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    arr[1]=arr[2]=arr[3]=1; //초기값
    for(int i=4; i<=116; i++) // 1<=N<=116
    {
        arr[i] = arr[i-1] + arr[i-3]; //점화식
    }
    cout << arr[N];
}

 

점화식이 문제에 주어져있다 (f(n) = f(n-1) + f(n-3))

주어진 점화식이 기존 피보나치 점화식을 말하는 건줄 알고 따로 규칙을 찾아 점화식을 작성하였다.

 

점화식이 주어져 있기 때문에 아주 간단하게 풀 수 있으나, 주의할 점은 점화식에 사용되는 배열을 long long으로 선언해줘야 한다.

N의 범위가 <=116까지이고, 이만큼 더해가는 과정에서 상당히 큰 수를 갖게 된다.

이를 생각안하고 int로 선언했다가 한 번 틀렸다.