[DP] 음수 피보나치 수열

음수 피보나치 수열

일반 피보나치 수열은 F(n) = F(n-1) + F(n-2) (단, n은 1보다 클 경우) 로 정의된다.

즉,

• F(0) = 0, F(1) = 1, F(2) = F(1) + F(0) = 1 ....... 로 확장된다.

0 이하에 대해서도 피보나치 수열 적용이 가능한데, 

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

즉, F(-1) = 1 이다. 이를 확장한다면  ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8... 의 순으로 진행된다.

규칙성을 보면 음수 방향으로 갈 때 각 짝수 Index 마다 마이너스가 붙어서 음수가 되는 것을 확인할 수 있다.

Value	-8	5	-3	2	-1	1	0
Index (-)	6	5	4	3	2	1	0

인덱스는 마이너스순으로 진행되지만 편의상 인덱스를 양수로 표시한다. 표로 보니 더 명확하게 보인다.

계산은 양수일 때 피보나치 수열로 하고 짝수 인덱스마다 -1을 곱해주면 되겠다.

 

Example Code

// 70만 되도 피보나치 수열 값은 190조가 넘어가기 때문에 long long 타입으로 지정한다.
long long arr[71]; // 문제의 최대값+1로 지정한다.
string fibo(int n)
{
    int num = abs(n); // 절대값으로 변경
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i <= num; i++)
    {
        arr[i] = arr[i-1] + arr[i-2];
    }
    // 음수일 때 (n이 짝수인 경우에만 -1을 곱해준다.) 
    if (n < 0 && num % 2 == 0)
    {
        return to_string(arr[num] * -1);
    }
    return to_string(arr[num]);
}