1788번

1788번 - 피보나치 수의 확장

처음에 양수는 양수대로, 음수는 음수대로 구하려고 했다.

양수는 F[N]=F[N-2] + F[N-1]  이라는 식을 쓰고, 

음수는 F[N-2] = F[N] - F[N-1] 이라는 식을 써서 풀려고 했다.. 그래서 배열도 늘리고 했는데 점점 복잡해져갔다..

(사실 내가 못했다.. 이렇게 푸신 분도 계심)

그래서 음수를 식에 따라 몇개를 구해보니, 그냥 피보나치 수열과 똑같았다.

다만 -2, -4 ,-6 이때만 음수값이 나오고 F[2]=-F[-2] 와 같았다.. 그래서 그냥 배열도 줄이고 절대값만을 이용해서 답을 구할 수 있었다.

<정답 코드>

#include<iostream>
 
using namespace std;
int n;
long long num[2000001];
 
 
int main()
{
    const int adjust = 1000000;
    const long long mod = 1000000000;
 
    scanf("%d", &n);
 
    num[0] = 0;
    num[1] = 1;
 
 
    for (int i = 2; i <= 1000000; i++)
    {
        num[i] = (num[i - 1]%mod + num[i - 2]%mod)%mod;
    }
 
 
    if (num[abs(n)] == 0)
    {
        printf("0\n");
        printf("%lld\n", abs(num[abs(n)]) % mod);
    }
    else
    {
        if (n < 0 && n % 2 == 0)
        {
            printf("-1\n");
        }
        else
        {
            printf("1\n");
        }
        printf("%lld\n", abs(num[abs(n)]) % mod);
    }
    
 
    return 0;
}