[BOJ 1788] 피보나치 수의 확장

https://www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

---

피보나치 수 F(n)에서 n이 음수의 경우에도 값을 구하는 문제이다.

 

-1부터 F(n)을 구하다 보면 값의 절대값이 대칭이 되는 것을 볼 수 있다.

 

F(n)이 음수인지, 양수인지, 0인지를 구하고 F(|n|)을 구하면 된다.

---

#include <stdio.h>

unsigned long long F[1000001] = { 0 ,1 };

int main()
{
	int n;
	scanf("%d", &n);

	if (n < 0)
	{
		printf("%d\n", n % 2 == 0? -1: 1);
		n *= -1;
	}
	else if (n > 0) printf("1\n");
	else printf("0\n");

	for (int i = 2; i <= n; i++)
		F[i] = F[i - 1] % 1000000000 + F[i - 2] % 1000000000;

	printf("%llu", F[n] % 1000000000);

}