백준 1788번: 피보나치 수의 확장

문제

문제 바로가기> 백준 1788번: 피보나치 수의 확장

풀이

몇 항만 적어보니 금방 규칙성을 찾을 수 있었다!

• |F(n)| = |F(-n)|
• n이 0 이하의 짝수인 경우 F(-n)의 부호는 -
• n이 0 이하의 홀수인 경우 F(-n)의 부호는 +

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

int n, sign=1, dp[MAX];

void solution(){
    // 부호 
    if(n<0) {
        if(n%2==0) sign=-1;
        n*=-1;
    }
    else if(n==0) sign=0;

    // dynamic programming
    dp[0]=0; dp[1]=1;
    for(int i=2; i<=n; i++) dp[i] = (dp[i-1]%MOD+dp[i-2]%MOD)%MOD;
    cout << sign << "\n" << dp[n];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    solution();
}