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

시간 제한 : 2초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
using namespace std;
long long dp[1000001] = { 0, 1, };
int main(void)
{
	int n, k;
	cin >> n;
	if (n < 0)
		k = -n;
	else
		k = n;
	for (int i = 2; i <= k; i++)
		dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000000;
	if (n > 0)
		cout << 1 << '\n' << dp[k] % 1000000000;
	else if (n == 0)
		cout << "0\n0";
	else
	{
		if ((-n) % 2 == 0)
			cout << -1 << '\n' << dp[k] % 1000000000;
		else
			cout << 1 << '\n' << dp[k] % 1000000000;
	}
	cout << '\n';
}

Tip

너무나 흔한 피보나치 수열이다, 음수 개념으로 확장했다고 해서 달라지는 것은 없다. 절대값을 씌우면 양수일 때와 똑같다. 배열을 한 번에 100만개 생성할 때는 힙 메모리(전역변수)에 메모리를 할당해주어야 할 수도 있다.