[백준] 1788번: 피보나치 수의 확장 - C++

문제

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

 

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

 

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

---

동적계획법으로 풀었던 문제.

 

음수라 당황했는데, F(0)부터 F(-5), F(-6)까지 나열하다보니 규칙이 보였다.

F(i) = F(i - 1) + F(i - 2) 일 때, 식을 옮겨서 표현하면 F(i - 2) = F(i) - F(i - 1)이므로,

 

F(-1) = F(1) - F(0) = 1

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

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

F(-4) = F(-2) - F(-3) = -3

F(-5) = F(-3) - F(-4) = 5

...

보다보면 N의 절댓값이 짝수일 때만 음수가 나오고, 홀수인 경우 기존의 피보나치수열과 동일하게 나오는 것을 확인할 수 있다.

따라서 N이 음수일 경우 위와 같은 케이스를 고려하여 양수로 바꿔준 뒤 동일하게 풀어주면 된다.

 

코드

#include <cstdio>
#define MOD 1000000000
#define MAX 1000001

long long DP(int num);

int main(void) {
    int n, flag = 1;
    scanf("%d", &n);

    if(n < 0) {
        n *= -1;
        if(n % 2 == 0) flag = -1;
    }
    
    if(n == 0) flag = 0;

    printf("%d\n%lld\n", flag, DP(n));
    return 0;
}

long long DP(int num) {
    long long arr[MAX];

    arr[0] = 0;
    arr[1] = 1;

    for(int i = 2; i <= num; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
    }

    return arr[num] % MOD;
}