백준 1788번: 피보나치 수의 확장 (C++)

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

1788번: 피보나치 수의 확장

---

Level: Silver III

Solved By: DP

 

음수에 관한 피보나치는 기존의 피보나치를 수정하여 간단하게 만들 수 있습니다. 또한, 이를 구하기 위한 DP를 사용하여 풀 수 있었습니다.

저는 양수 피보나치, 음수 피보나치를 따로 배열을 선언하여 문제를 풀었습니다.

#include <iostream>
#include <cmath>
#define MAX 1000001
#define MOD 1000000000
using namespace std;

int cache[MAX];
int cache_[MAX];

void print_(int n){
    if(n == 0) cout << 0;
    else if(n > 0) cout << 1;
    else cout << -1;
    cout << '\n';
    
    cout << abs(n);
}

int main(){
    int N; cin >> N;
    if(N == 0){
        print_(0);
    }
    else if(N > 0){
        cache[1] = 1;
        for(int i = 2; i <= N; i++){
            cache[i] = (cache[i-1]%MOD + cache[i-2]%MOD)%MOD;
        }
        print_(cache[N]);
    }
    else{
        N = abs(N);
        cache_[1] = 1;
        for(int i = 2; i <= N; i++){
            cache_[i] = (cache_[i-2]%MOD - cache_[i-1]%MOD)%MOD;
        }
        print_(cache_[N]);
    }
    return 0;
}