14495번

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

그냥 짰더니 시간초과가 발생하여 DP 로 접근하여 문제를 풀 수 있었다.

그리고 int 형을 초과하기 때문에 long long 타입으로 바꿔줘야 AC를 받을 수 있었다.

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
 
long long D[117];
 
long long fibo(int n)
{
    if (n <= 0)
    {
        return 0;
    }
 
    if (n == 1 || n == 2 || n == 3)
    {
        return 1;
    }
 
    if (D[n] >= 0)
    {
        return D[n];
    }
 
    if (D[n] == -1)
    {
        D[n] = 0;
    }
    
    D[n] += fibo(n - 1) + fibo(n - 3);
 
    return D[n];
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    memset(D, -1, sizeof(D));
    cout << fibo(n);
    
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}