[백준 1788] 피보나치 수의 확장 [C]

백준 - 1788

---

풀이

F(1) = 1 = F(0) + F(-1), F(-1) = 1

F(0) = 0 = F(-1) + F(-2), F(-2) = -1

F(-1) = 1 = F(-2) + F(-3), F(-3) = 2

F(-2) = -1 = F(-3) + F(-4), F(-4) = -3

F(-3) = 2 = F(-4) + F(-5), F(-5) = 5

 

n이 음수이고, 짝수일때만, F(n)이 -1이다.

---

소스코드

#include <stdio.h>
int main(){
    int n, op = 1;
    long long dp[2] = {0, 1};
    scanf("%d", &n);
    if (n < 0){
        if (n%2 == 0) op = -1;
        n *= -1;
    }else op = (n ? 1 : 0);
    if (n >= 2){
        for (int i = 1; i < n; i++){
            long long temp = (dp[0] + dp[1]) %1000000000;
            dp[0] = dp[1], dp[1] = temp;
        }
        n = 1;
    }
    printf("%d\n%lld", op, dp[n]);
}

---

출처

1788번: 피보나치 수의 확장